Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Shortest Path Algorithms > Dijkstra's Algorithm for SSSP > Example DIJKSTRA()

Example of How to Use DIJKSTRA()

The following program shows how the function DIJKSTRA() can be used to compute single source shortest paths in a directed graph with non-negative edge costs.

Remark: The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs.

In main() we first create a simple graph G with four nodes and six edges.

The costs of the edges are stored in the edge_array<int> cost. We use int as the number type for the edge costs. The variant of DIJKSTRA() for double can be used in exactly the same way. You only need to replace int by double in the definition of cost and dist.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/shortest_path.h>

using namespace leda;

int main()
  graph G; 

  node n0=G.new_node(); node n1=G.new_node();
  node n2=G.new_node(); node n3=G.new_node();

  edge e0=G.new_edge(n0,n1); edge e1=G.new_edge(n0,n2);
  edge e2=G.new_edge(n1,n2); edge e3=G.new_edge(n1,n3);
  edge e4=G.new_edge(n2,n3); edge e5=G.new_edge(n3,n1);
  edge_array<int> cost(G);
  cost[e0]=1; cost[e1]=2; cost[e2]=3;
  cost[e3]=4; cost[e4]=5; cost[e5]=6;

The node_array<edge> pred and the node_array<int> dist for G are used for the result of DIJKSTRA(). pred[v] will contain the last edge on a shortest path from the source node s to v. This allows a construction of the complete shortest path. dist[v] will contain the length of a shortest path from s to v.

  node_array<edge> pred(G);  
  node_array<int> dist(G);
  node v;
  forall_nodes(v,G) {
    if (v==n0) 
	std::cout << " was source node." << std::endl;
	if (pred[v]==nil) 
	  std::cout << " is unreachable." << std::endl;
      else {
        std::cout << " " << dist[v] << " "; 
        std::cout << std::endl;

  return 0;

See also:

Dijkstra's Algorithm for SSSP


Parameterized Graphs

Edge Arrays

Node Arrays

Checking the Results of an SSSP Algorithm

Graphs and Related Data Types

Manual Entries:

Manual Page Shortest Path Algorithms

Please send any suggestions, comments or questions to
© Copyright 2001-2003, Algorithmic Solutions Software GmbH