Dijkstra's algorithm finds minimum-weight paths from a source vertex through a weighted graph. It suits irregular maps where distance cannot be approximated by counting edges, provided every edge has nonnegative weight. section 14.0 section 14.4
The algorithm proceeds by maintaining tentative distances and a frontier ordered by distance:
- Initialize the source distance to zero, every other distance to infinity, and each predecessor to null. section 14.4.2
- Insert the source into a min-priority queue, repeatedly extract the closest discovered vertex, and optionally stop when it satisfies the goal condition. section 14.4.1 section 14.4.2
- Relax each outgoing edge: replace a neighbor's tentative distance when the route through the current vertex is shorter, then update its predecessor and queue priority. section 14.4.2 section 14.4.3
- Reconstruct the route by following predecessor links from the destination back to the source. section 14.4.2 section 14.4.4
Choosing distance over edge count
In a weighted graph, a two-edge route from v1 through v3 to v2 can weigh 8, while a three-edge route through v5 can weigh 5. Dijkstra's algorithm first records 8, then lowers the tentative distance to 5 when the better route is discovered. section 14.4.3
Listing 14.6 Dijkstra’s algorithm
function dijkstra(graph, start, isGoal) #1
queue ← new PriorityQueue() #2
queue.insert(start, 0) #3
distances[v] ← inf (∀ v ϵ graph | v <> start) #4
parents[v] ← null (∀ v ϵ graph) #5
distances[start] ← 0 #6
while not queue.empty() do #7
v ← queue.top() #8
if isGoal(v) then #9
return (v, parents)
else
for e in graph.adjacencyList[v] do #10
u ← e.dest
if distances[u] > distances[v] + e.weight then #11
distances[u] ← e.weight + distances[v] #12
parents[u] ← v
queue.update(u, distances[u])
return (null, parents) #13
Use the implementation listing to trace initialization, priority-queue processing, relaxation, and predecessor updates. section 14.4.2
A plain queue is insufficient because a path with more edges can have lower total weight. With an array priority queue, running time is O(|E|*|V|); with a heap it is O(|E|*log(|V|)); with a Fibonacci heap it is O(|V|*log(|V|)+|E|) amortized. Negative-weight edges invalidate the greedy assumption. section 14.4.3 section 14.4.4
