DIJKSTRA

Dijkstra’s Algorithm

#include <LEDA/graph.h>

#include <LEDA/node_pq.h>

void DIJKSTRA (graph& G, node s,

edge_array<int>& cost,

node_array<int>& dist,

node_array<int>& pred )

{

node_pq<int> PQ(G);

int c;

node u, v;

edge e;

forall_nodes(v,G) {

pred[v] = 0;

dist[v] = infinity;

PQ.insert(v, dist[v]);

}

dist[s] = 0;

PQ.decrease_inf(s, 0);

while ( ! PQ.empty()) {

u = PQ.del_min();

forall_adj_edges(e,u) {

v = G.target(e);

c = dist[u] + cost[e];

if (c < dist[v]) {

dist[v]=c; pred[v]=u;

PQ.decrease_inf(v,c);

} // if

} // forall)adj_edges

} // while

}

Previous slide

Back to first slide

View graphic version