Shortest distances from 0 on a directed weighted graph. Every vertex starts at infinity except 0 at 0. Repeat: settle the unsettled vertex with the smallest distance, then relax its edges. With no negative weights, a settled distance can never be beaten.
Dijkstra's algorithm from vertex 0.
Unsettled vertices with a known distance: 0 at 0. The smallest is 0, so settle it: 0 is final, because every other route into 0 would pass through something at least as far and edges never shorten a path.
Vertex 0 is settled at distance 0.
Relax 0 to 1: 0 + 4 = 4 against 1's current infinity. Shorter, so 1 becomes 4 with 0 as its parent.
Edge 0 to 1: 4 against infinity. Improved.
Relax 0 to 2: 0 + 1 = 1 against 2's current infinity. Shorter, so 2 becomes 1 with 0 as its parent.
Edge 0 to 2: 1 against infinity. Improved.
Unsettled vertices with a known distance: 2 at 1, 1 at 4. The smallest is 2, so settle it: 1 is final, because every other route into 2 would pass through something at least as far and edges never shorten a path.
Vertex 2 is settled at distance 1.
Relax 2 to 1: 1 + 2 = 3 against 1's current 4. Shorter, so 1 becomes 3 with 2 as its parent.
Edge 2 to 1: 3 against 4. Improved.
Relax 2 to 3: 1 + 5 = 6 against 3's current infinity. Shorter, so 3 becomes 6 with 2 as its parent.
Edge 2 to 3: 6 against infinity. Improved.
Unsettled vertices with a known distance: 1 at 3, 3 at 6. The smallest is 1, so settle it: 3 is final, because every other route into 1 would pass through something at least as far and edges never shorten a path.
Vertex 1 is settled at distance 3.
Relax 1 to 3: 3 + 1 = 4 against 3's current 6. Shorter, so 3 becomes 4 with 1 as its parent.
Edge 1 to 3: 4 against 6. Improved.
Unsettled vertices with a known distance: 3 at 4. The smallest is 3, so settle it: 4 is final, because every other route into 3 would pass through something at least as far and edges never shorten a path.
Vertex 3 is settled at distance 4.
Relax 3 to 4: 4 + 3 = 7 against 4's current infinity. Shorter, so 4 becomes 7 with 3 as its parent.
Edge 3 to 4: 7 against infinity. Improved.
Unsettled vertices with a known distance: 4 at 7. The smallest is 4, so settle it: 7 is final, because every other route into 4 would pass through something at least as far and edges never shorten a path.
Vertex 4 is settled at distance 7.
Distances from 0: 0: 0, 1: 3, 2: 1, 3: 4, 4: 7. The highlighted edges are the shortest-path tree. 6 relaxations. With a heap for the minimum this is O((V + E) log V).
Dijkstra finished. vertex 0 at 0, vertex 1 at 3, vertex 2 at 1, vertex 3 at 4, vertex 4 at 7.