1 of 15

Dijkstra’s Algorithm

(Shortest Path)

2 of 15

Dijkstra(Vertex source):

for each vertex v:

set v.cost = infinity

mark v as unvisited

​

set source.cost = 0

​

while exist unvisited vertices:

select unvisited vertex v with lowest cost

mark v as visited

​

for each edge (v, u) with weight w:

if u is not visited:

potentialBest = v.cost + w // cost of best path to u through v

currBest = u.cost // cost of current best path to u

​

if (potentialBest < currBest):

u.cost = potentialBest

u.pred = v

Dijkstra’s Algorithm

Dijkstra’s algorithm finds the minimum-cost path from a source vertex to every other vertex in a non-negatively weighted graph

  • O(|V| log |V| + |E| log |V|) runtime

3 of 15

Problem 0

Dijkstra(Vertex source):

for each vertex v:

set v.cost = infinity

mark v as unvisited

​

set source.cost = 0

​

while exist unvisited vertices:

select unvisited vertex v with lowest cost

mark v as visited

​

for each edge (v, u) with weight w:

if u is not visited:

potentialBest = v.cost + w

currBest = u.cost

​

if (potentialBest < currBest):

u.cost = potentialBest

u.pred = v

4 of 15

Problem 0 (1)

Vertex

Visited?

Cost

Predecessor

A

​

​

–

B

​

​

–

C

​

​

–

D

​

​

–

E

​

​

–

F

​

​

–

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

  • Initialize each vertex as unvisited with cost ∞
  • Set cost of source vertex A to 0

∞

∞

∞

∞

∞

∞

0

No

No

No

No

No

No

5 of 15

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

A

1

8

16

13

50

Vertex

Visited?

Cost

Predecessor

A

No

0

–

B

No

∞

–

C

No

∞

–

D

No

∞

–

E

No

∞

–

F

No

∞

–

  • Select unvisited vertex with lowest cost (A)

Yes

  • Mark A as visited
  • Process each outgoing edge

∞ 8

∞ 16

∞ 50

∞ 13

∞ 1

A

A

A

A

A

Problem 0 (2)

6 of 15

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

3

13

Vertex

Visited?

Cost

Predecessor

A

Yes

0

–

B

No

∞ 8

A

C

No

∞ 16

A

D

No

∞ 50

A

E

No

∞ 13

A

F

No

∞ 1

A

Yes

A

F

∞ 13 4

  • Select unvisited vertex with lowest cost (F)
  • Mark F as visited
  • Process each outgoing edge

A F

Problem 0 (3)

7 of 15

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

5

Vertex

Visited?

Cost

Predecessor

A

Yes

0

–

B

No

∞ 8

A

C

No

∞ 16

A

D

No

∞ 50

A

E

No

∞ 13 4

A F

F

Yes

∞ 1

A

E

∞ 50 9

Yes

A

  • Select unvisited vertex with lowest cost (E)
  • Mark E as visited
  • Process each outgoing edge

F

A E

Problem 0 (4)

8 of 15

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

Vertex

Visited?

Cost

Predecessor

A

Yes

0

–

B

No

∞ 8

A

C

No

∞ 16

A

D

No

∞ 50 9

A E

E

Yes

∞ 13 4

A F

F

Yes

∞ 1

A

B

Yes

A

  • Select unvisited vertex with lowest cost (B)
  • Mark B as visited
  • Process each outgoing edge

F

E

  • No outgoing edges; continue

Problem 0 (5)

9 of 15

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

2

Vertex

Visited?

Cost

Predecessor

A

Yes

0

–

B

Yes

∞ 8

A

C

No

∞ 16

A

D

No

∞ 50 9

A E

E

Yes

∞ 13 4

A F

F

Yes

∞ 1

A

D

Yes

A D

A

  • Select unvisited vertex with lowest cost (D)
  • Mark D as visited
  • Process each outgoing edge

(ignore D→B since B is already visited)

F

E

B

∞ 16 11

6

Problem 0 (6)

10 of 15

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

7

Vertex

Visited?

Cost

Predecessor

A

Yes

0

–

B

Yes

∞ 8

A

C

No

∞ 16 11

A D

D

Yes

∞ 50 9

A E

E

Yes

∞ 13 4

A F

F

Yes

∞ 1

A

C

Yes

A

  • Select unvisited vertex with lowest cost (C)
  • Mark C as visited
  • Process each outgoing edge

(ignore C→B & C→E since B & E are already visited)

​

F

E

B

D

  • No outgoing edges to unvisited nodes; continue

3

Problem 0 (7)

11 of 15

F

A

D

C

B

E

1

3

5

2

8

16

13

13

50

6

3

7

Vertex

Visited?

Cost

Predecessor

A

Yes

0

–

B

Yes

∞ 8

A

C

No

∞ 16 11

A D

D

Yes

∞ 50 9

A E

E

Yes

∞ 13 4

A F

F

Yes

∞ 1

A

Yes

A

F

E

B

D

C

  • No more unvisited nodes; we are done

Problem 0 (8)

12 of 15

Problem 1

Dijkstra(Vertex source):

for each vertex v:

set v.cost = infinity

mark v as unvisited

​

set source.cost = 0

​

while exist unvisited vertices:

select unvisited vertex v with lowest cost

mark v as visited

​

for each edge (v, u) with weight w:

if u is not visited:

potentialBest = v.cost + w

currBest = u.cost

​

if (potentialBest < currBest):

u.cost = potentialBest

u.pred = v

13 of 15

Problem 1 (1)

Vertex

Visited?

Cost

Predecessor

A

​

​

–

B

​

​

–

C

​

​

–

D

​

​

–

E

​

​

–

F

​

​

–

B

A

D

E

F

C

5

3

-5

10

4

60

70

80

90

6

7

  • Initialize each vertex as unvisited with cost ∞
  • Set cost of source vertex A to 0

∞

∞

∞

∞

∞

∞

0

No

No

No

No

No

No

14 of 15

B

A

D

E

F

C

5

3

-5

10

4

60

70

80

90

6

7

  • Initialize each vertex as unvisited with cost ∞
  • Set cost of source vertex A to 0

Vertex

Visited?

Cost of Path

Pred

a

True

0

​

b

True

∞ 05

a

c

True

∞ 80 08

a b

d

True

∞ 90 03

a c

e

True

∞ 60 13

a d

f

True

∞ 04

a

​

Order added to known set: a, f, b, c, d, e

Problem 1 (2)

15 of 15

Thank You!