Dijkstra's Shortest Path Algorithm
Reached, not settled
Empty.
Settled, cheapest first
Nothing yet.
- Not reached
- Waiting
- Current
- Finished
1/20
A is 0 away from itself. Everything else starts at infinity.
Settings
Graph
More options
Dijkstra
- 1
dist[start] = 0, everything else inf - 2
while unsettled nodes remain: - 3
node = closest unsettled node - 4
settle(node) - 5
for each neighbour: - 6
d = dist[node] + weight - 7
if d < dist[neighbour]: - 8
dist[neighbour] = d
What Each One Answers
| Algorithm | What it answers | Time | Needs |
|---|---|---|---|
| Breadth-First | Fewest hops from the start | O(V + E) | A queue |
| Depth-First | Reachability, one branch at a time | O(V + E) | A stack |
| Cycle Detection | Whether there is a cycle, and where | O(V + E) | Node colours |
| Topological Sort | A valid order to do the work in | O(V + E) | No cycles |
| Dijkstra | Cheapest path by edge weight | O(E log V) | Non-negative weights |
Scroll the table sideways for the rest of the columns.
V is the number of nodes and E the number of edges. On the graph with a cycle, topological sort gets stuck, because a cycle leaves no valid order.