Given the following weighted directed graph, use Dijkstra’s algorithm to find…

Graph edges with weights:

A -> B (4)
A -> C (1)
C -> B (2)
C -> D (4)
B -> E (4)
D -> E (4)

Step 1: Initialization

Source vertex = A

Distances:
A = 0
B = infinity
C = infinity
D = infinity
E = infinity

Visited set = { }

Step 2: Visit A

Relax outgoing edges from A:

B = min(infinity, 0 + 4) = 4
C = min(infinity, 0 + 1) = 1

Distances now:
A = 0, B = 4, C = 1, D = infinity, E = infinity

Next vertex = C, because it has the smallest temporary distance.

Step 3: Visit C

Relax outgoing edges from C:

B = min(4, 1 + 2) = 3
D = min(infinity, 1 + 4) = 5

Distances now:
A = 0, B = 3, C = 1, D = 5, E = infinity

Next vertex = B.

Step 4: Visit B

Relax outgoing edge from B:

E = min(infinity, 3 + 4) = 7

Distances now:
A = 0, B = 3, C = 1, D = 5, E = 7

Next vertex = D.

Step 5: Visit D

Relax outgoing edge from D:

E = min(7, 5 + 4) = min(7, 9) = 7

So there is no change.

Final shortest distances and paths from A:

A: distance 0, path A
C: distance 1, path A -> C
B: distance 3, path A -> C -> B
D: distance 5, path A -> C -> D
E: distance 7, path A -> C -> B -> E