Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Shortest Path Algorithms > SSSP Algorithms for Acyclic Shortest Paths > Example ACYCLIC_SHORTEST_PATH()

Example of How to Use ACYCLIC_SHORTEST_PATH()

The following program shows how the function ACYCLIC_SHORTEST_PATH() can be used to compute single source shortest paths in a directed acyclic graph.

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 six nodes and six edges.

The costs of the edges are stored in the edge_array<int> cost. In this example, we use int as the number type for the edge costs. The variant of ACYCLIC_SHORTEST_PATH() 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();
  node n4=G.new_node(); node n5=G.new_node();

  edge e0=G.new_edge(n0,n1); edge e1=G.new_edge(n0,n2);
  edge e2=G.new_edge(n2,n3); edge e3=G.new_edge(n3,n4);
  edge e4=G.new_edge(n2,n4); edge e5=G.new_edge(n3,n5);
 
  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 ACYCLIC_SHORTEST_PATH(). 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);
  ACYCLIC_SHORTEST_PATH(G,n0,cost,dist,pred);
 
  node v;
  forall_nodes(v,G) {
    G.print_node(v);
    if (v==n0) 
      std::cout << " was source node." << std::endl;
    else 
      if (pred[v]==nil) 
        std::cout << " is unreachable." << std::endl;
      else {
        std::cout << " " << dist[v] << " "; 
        G.print_edge(pred[v]);
        std::cout << std::endl;
      }
  }

  return 0;
}

See also:

SSSP Algorithms for Acyclic Shortest Paths

Graphs

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 leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH