Algorithms R OBERT S EDGEWICK | K EVIN W AYNE

D IJKSTRA ' S A LGORITHM D EMO

Algorithms F O U R T H E D I T I O N

R OBERT S EDGEWICK | K EVIN W AYNE

[Link]
 Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3 0→1 5.0
15
0→4 9.0
5
4 0→7 8.0
12
s 0 3 1→2 12.0
8 1→3 15.0
7 2 9
7 1→7 4.0
9 2→3 3.0
6 1
11 2→6 11.0
5
5 3→6 9.0
4 13 4→5 4.0
4→6 20.0
4 20 6
4→7 5.0
5→2 1.0
5→6 13.0
an edge-weighted digraph 7→5 6.0
7→2 7.0
2
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1
2
7 2 3
4
5
5 6
7

4 6

choose source vertex 0

3
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
∞
1 3
v distTo[] edgeTo[]
0 5 0 0.0 -
0 1
8 ∞ 2
7 2 3
9 4
5
5 6
7

4 6

relax all edges pointing from 0

4
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
∞ 5

1 3
v distTo[] edgeTo[]
0 5 0 0.0 -
0 1 5.0 0→1
8 ∞ 8 2
7 2 3
9 4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

∞ 9

relax all edges pointing from 0

5
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2
7 2 3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

6
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2
7 2 3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

choose vertex 1

7
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
5 ∞
1 15 3
v distTo[] edgeTo[]
0 0.0 -
4
12
0 1 5.0 0→1
8 2
7 2 ∞ 3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

relax all edges pointing from 1

8
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
5 ∞ 20

1 15 3
v distTo[] edgeTo[]
0 0.0 -
4
12
0 1 5.0 0→1
8 2 17.0 1→2
7 2 ∞ 17 3 20.0 1→3
4 9.0 0→4
5
5 6
7 8.0 ✔ 0→7

4 6

relax all edges pointing from 1

9
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 17.0 1→2
7 2 3 20.0 1→3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

10
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 17.0 1→2
7 2 3 20.0 1→3
4 9.0 0→4
5
5 6
7 8.0 0→7

4 6

choose vertex 7

11
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
8 2 17.0 1→2
17
7 7 2 3 20.0 1→3

6 4 9.0 0→4
5
5 6

∞ 7 8.0 0→7

4 6

relax all edges pointing from 7

12
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
8 2 15.0 7→2
17 15
7 7 2 3 20.0 1→3

6 4 9.0 0→4
5 14.0 7→5
5 6

∞ 14 7 8.0 0→7

4 6

relax all edges pointing from 7

13
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 14.0 7→5
5 6
7 8.0 0→7

4 6

14
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 14.0 7→5
5 6
7 8.0 0→7

4 6

select vertex 4

15
 Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
8 2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 14.0 7→5
5
5 14 6
4 7 8.0 0→7

9 4 20 6 ∞

relax all edges pointing from 4

16
 Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
8 2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5
5 14 13 6 29.0 4→6
4 7 8.0 ✔ 0→7

9 4 20 6 ∞ 29

relax all edges pointing from 4

17
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 29.0 4→6
7 8.0 0→7

4 6

18
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 15.0 7→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 29.0 4→6
7 8.0 0→7

4 6

select vertex 5

19
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 15.0 7→2
7 2 15 3 20.0 1→3
4 9.0 0→4
1
5 13.0 4→5
5 6 29.0 4→6
13 7 8.0 0→7
13
4 6 29

relax all edges pointing from 5

20
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 15 14 3 20.0 1→3
4 9.0 0→4
1
5 13.0 4→5
5 6 26.0 5→6
13 7 8.0 0→7
13
4 6 29 26

relax all edges pointing from 5

21
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

22
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 20.0 1→3
4 9.0 0→4
5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6

select vertex 2

23
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
20

1 3
v distTo[] edgeTo[]
0 0.0 -
0 3 1 5.0 0→1
2 14.0 5→2
7 2 14 3 20.0 1→3
4 9.0 0→4
11 5 13.0 4→5
5 6 26.0 5→6
7 8.0 0→7

4 6 26

relax all edges pointing from 2

24
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
20 17

1 3
v distTo[] edgeTo[]
0 0.0 -
0 3 1 5.0 0→1
2 14.0 5→2
7 2 14 3 17.0 2→3
4 9.0 0→4
11 5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6 26 25

relax all edges pointing from 2

25
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

26
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

select vertex 3

27
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
20

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 9
3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6 25

relax all edges pointing from 3

28
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.
20

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 9
3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 ✔ 2→6
7 8.0 0→7

4 6 25

relax all edges pointing from 3

29
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

30
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

select vertex 6

31
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

relax all edges pointing from 6

32
Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

33
 Dijkstra's algorithm demo

Consider vertices in increasing order of distance from s

(non-tree vertex with the lowest distTo[] value).
Add vertex to tree and relax all edges pointing from that vertex.

1 3
v distTo[] edgeTo[]
0 0.0 -
s 0 1 5.0 0→1
2 14.0 5→2
7 2 3 17.0 2→3
4 9.0 0→4
5 13.0 4→5
5 6 25.0 2→6
7 8.0 0→7

4 6

shortest-paths tree from vertex s

34