Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Shortest Path Algorithms > Generic Algorithms for SSSP > Example SHORTEST_PATH_T()

Example of How to Use SHORTEST_PATH_T()

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

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

In order to use the template function SHORTEST_PATH_T() we need to include <LEDA/templates/shortest_path.t>. We use the LEDA number type integer as the number type NT for the edge costs. In constrast to the C++ number type int, LEDA's integer does not overflow.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/templates/shortest_path.h>
#include <LEDA/numbers/integer.h>

using namespace leda;

In main() we first create a simple graph G with four nodes and five edges. We use an edge_array<integer> cost to store the costs of the edges of G.

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,n3);
  edge e2=G.new_edge(n1,n2); edge e3=G.new_edge(n2,n3);
  edge e4=G.new_edge(n3,n1);
 
  edge_array<integer> cost(G);
  cost[e0]=1; cost[e1]=-1; cost[e2]=-1;
  cost[e3]=2; cost[e4]=1;

The node_array<edge> pred and the node_array<integer> dist are used for the result of SHORTEST_PATH_T(). If there are no negative cost cycles reachable from n0, pred[v] will contain the last edge on a shortest path from the source node n0 to v. This allows a construction of the complete shortest path. dist[v] will contain the length of a shortest path from n0 to v. If there are negative cost cycles, SHORTEST_PATH_T() returns false. In this case all dist-values are unspecified. One can use the functions for checking the results of an SSSP algorithm to get more details about the result.

  node_array<edge> pred(G);
  node_array<integer> dist(G);

  bool no_negative_cycle_reachable_from_s = SHORTEST_PATH_T(G,n0,cost,dist,pred);

  if (no_negative_cycle_reachable_from_s) {
    node v; 
    
    forall_nodes(v,G) {
      G.print_node(v);
      if (pred[v]==nil&&v!=n0) 
        std::cout << " is not reachable from s!" << std::endl;
      else if (v!=n0) {
        G.print_edge(pred[v]);
        std::cout << " " << dist[v] << std::endl; 
      }
      else std::cout << " was source node" << std::endl;
    }
  }

  else std::cout << "Negative cycle reachable from s!"
                 << " Result invalid!" << std::endl;
  
  return 0;
}

See also:

Generic Algorithms for SSSP

Checking the Results of an SSSP Algorithm

Integer

Graphs

Parameterized Graphs

Edge Arrays

Node Arrays


Number Types

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