Example of How to Use DIJKSTRA()
The following program shows how the function DIJKSTRA()
can be used to compute single source shortest paths in a directed graph
with non-negative edge costs.
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 six 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 DIJKSTRA() 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();
edge e0=G.new_edge(n0,n1); edge e1=G.new_edge(n0,n2);
edge e2=G.new_edge(n1,n2); edge e3=G.new_edge(n1,n3);
edge e4=G.new_edge(n2,n3); edge e5=G.new_edge(n3,n1);
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 DIJKSTRA().
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);
DIJKSTRA(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;
}
|