Example of How to Use ACYCLIC_SHORTEST_PATH_T()
The following program shows how the function ACYCLIC_SHORTEST_PATH_T()
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 order to use the template function ACYCLIC_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 six nodes and six 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();
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<integer> 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<integer> dist are used
for the result of ACYCLIC_SHORTEST_PATH_T(). 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<integer> dist(G);
ACYCLIC_SHORTEST_PATH_T(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;
}
|