Dijkstra's algorithm finds shortest paths from one source through a weighted graph whose edge costs are nonnegative. Unlike BFS or DFS, it optimizes cumulative distance, making it useful for routing from home to work or between map locations. section 3.2 section 3.4
The search maintains distances and predecessors while repeatedly expanding the currently closest unrelaxed node:
- Initialize every distance to infinity, set the source distance to zero, and place nodes in the unrelaxed set. section 3.4.1
- Select the node with the smallest cumulative distance, mark it seen, and inspect each child. section 3.4.1
- Relax each edge: replace a child's distance and predecessor when the route through the current node is shorter. section 3.4.1
- Continue until the relevant nodes are processed, then retrace predecessors to recover the route. section 3.4.1 section 3.5
A small route
Starting at S, the algorithm first processes S, then C, D, and A as their cumulative distances become smallest, updating predecessors and eventually reaching B. On map data, parallel edges should be reduced to the lowest-weight edge and self-loops ignored; NetworkX provides dijkstra_path for weighted routes. section 3.4.1 section 3.5
Algorithm 3.3 Dijkstra’s algorithm
Inputs: A graph with weighted edges and a source node Output: Shortest path from the source to all other nodes in the graph Initialize shortest_dist ← empty Initialize unrelaxed_nodes ← empty Initialize seen ← empty For node in graph Set shortest_dist[node] = Infinity Add node to unrelaxed_nodes Set shortest_dist[source] ← 0 While unrelaxed_nodes is not empty do Set node ← unrelaxed_nodes.pop() Add node to seen For child in node.expand() do If child in seen then skip Update distance ← shortest_dist[node] + length of edge to child If distance < shortest_dist[child] then Update shortest_dist[child] ← distance Update child.parent ← node Return shortest_dist
Use the pseudocode to follow initialization, node expansion, edge relaxation, and predecessor updates. section 3.4.1
