Example of How to Use ALL_PAIRS_SHORTEST_PATHS_T()
The following program shows how the function ALL_PAIRS_SHORTEST_PATHS_T()
can be used to compute the lengths of the shortest paths between all pairs
of nodes in a directed graph. Edge costs may be positive or negative.
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 ALL_PAIRS_SHORTEST_PATHS_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_matrix<integer>
dist is used for the result of ALL_PAIRS_SHORTEST_PATHS_T() .
dist(v,w) will contain the length of a shortest path from
v to w if there are no negative cycles in G .
node_matrix<integer> dist(G);
bool no_negative_cycle=ALL_PAIRS_SHORTEST_PATHS_T(G,cost,dist);
if (no_negative_cycle) {
node v;
forall_nodes(v,G) {
node w;
forall_nodes(w,G) {
if (v!=w) {
std::cout << "The distance from "; G.print_node(v);
std::cout << " to "; G.print_node(w);
std::cout << " is " << dist(v,w) << std::endl;
}
}
}
}
else std::cout << "There are negative cycles!" << std::endl
<< "All dist-values unspecified!" << std::endl;
return 0;
}
|