Dijkstra's algorithm: Difference between revisions

This implementation finds the single path from a source to all reachable vertices.

Building the graph from a set of edges takes O(E log V) for each pass.

Decreasing the distance of a vertex is accomplished by removing it from the heap and later re-inserting it.

<lang java>

import java.io.*;

}

final Vertex source = graph.get(startName);

// set-up vertices

}

Vertex u, v;

while (!q.isEmpty()) {

if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable