Example of How to Use SHORTEST_PATH()
The following program shows how the function SHORTEST_PATH()
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 main() we first create a simple graph G
with four nodes and five 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 SHORTEST_PATH() for double can be used in
exactly the same way. You only need to replace int by double
in 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(n1,n2);
edge e2=G.new_edge(n0,n2); edge e3=G.new_edge(n0,n3);
edge_array<int> cost(G);
cost[e0]=1; cost[e1]=1;
cost[e2]=3; cost[e3]=1;
The node_array<edge>
pred and the node_array<int> dist for G
are used for the result of SHORTEST_PATH(). 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() 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<int> dist(G);
bool no_negative_cycle_reachable_from_s = SHORTEST_PATH(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;
}
|