Using Dijkstra’s Algorithm from source vertex S.
Step 1: Initialize distances
Verte Distance
x from S
S 0
a ∞
b ∞
c ∞
d ∞
e ∞
Step-by-step execution
Visit S
Edges from S:
S→a=1
S→b=5
Update:
a=1
b=5
Visited order: S
Visit a (smallest distance = 1)
Edges from a:
a→b=2
a→c=2
a→d=1
Update:
b = min(5, 1+2) = 3
c = 1+2 = 3
d = 1+1 = 2
Visited order: S, a
Visit d (smallest distance = 2)
Edges from d:
d→e=2
d→c=3
Update:
e = 2+2 = 4
c = min(3, 2+3=5) = 3
Visited order: S, a, d
Visit b (distance = 3)
No shorter paths obtained.
Visited order: S, a, d, b
Visit c (distance = 3)
Edge:
c→e=1
Update:
e = min(4, 3+1=4) = 4
Visited order: S, a, d, b, c
Visit e (distance = 4)
Visited order: S, a, d, b, c, e
Final Shortest Distances from S
Verte Shortest
x Distance
a 1
b 3
c 3
d 2
e 4
Order of Visiting Vertices
S → a →d → b →c → e
(If vertices with equal distance are chosen differently, c and b may interchange.)
step by step solving of above problem
Dijkstra’s Algorithm – Step by Step Solution
Given Graph
Edges and weights:
S→a=1
S→b=5
a→b=2
a→c=2
a→d=1
b→d=2
c→d=3
c→e=1
d→e=2
Step 1: Initialize
Source vertex = S
Set distance of source as 0 and all others as ∞.
Verte Distan Previo
x ce us
S 0 —
a ∞ —
b ∞ —
c ∞ —
d ∞ —
e ∞ —
Visited vertices = { }
Step 2: Visit S
Current vertex = S (minimum distance = 0)
Neighbors of S:
S→a=1
New distance = 0 + 1 = 1
Update a = 1
S→b=5
New distance = 0 + 5 = 5
Update b = 5
Updated table:
Verte Distan Previo
x ce us
S 0 —
a 1 S
b 5 S
c ∞ —
d ∞ —
e ∞ —
Visited = { S }
Step 3: Visit a
Choose smallest unvisited distance:
a=1
Current vertex = a
Neighbors of a:
a→b=2
New distance = 1 + 2 = 3
Current b = 5
Since 3 < 5, update:
b=3
a→c=2
New distance = 1 + 2 = 3
Update:
c=3
a→d=1
New distance = 1 + 1 = 2
Update:
d=2
Updated table:
Verte Distan Previo
x ce us
S 0 —
a 1 S
b 3 a
c 3 a
d 2 a
e ∞ —
Visited = { S, a }
Step 4: Visit d
Smallest unvisited distance:
d=2
Current vertex = d
Neighbors of d:
d→e=2
New distance = 2 + 2 = 4
Update:
e=4
Updated table:
Verte Distan Previo
x ce us
S 0 —
a 1 S
b 3 a
c 3 a
d 2 a
Verte Distan Previo
x ce us
e 4 d
Visited = { S, a, d }
Step 5: Visit b
Smallest unvisited distance:
b=3
Current vertex = b
Neighbor:
b→d=2
New distance = 3 + 2 = 5
Current d = 2
Since 5 > 2, no update.
Table remains same.
Visited = { S, a, d, b }
Step 6: Visit c
Next smallest:
c=3
Current vertex = c
Neighbors of c:
c→d=3
New distance = 3 + 3 = 6
Current d = 2
No update.
c→e=1
New distance = 3 + 1 = 4
Current e = 4
Equal distance, so no change.
Updated table:
Verte Distan Previo
x ce us
S 0 —
a 1 S
b 3 a
c 3 a
d 2 a
e 4 d
Visited = { S, a, d, b, c }
Step 7: Visit e
Current vertex = e
No further updates.
Visited = { S, a, d, b, c, e }
Final Shortest Distances
Verte Shortest Distance
x from S
a 1
b 3
c 3
d 2
e 4
Shortest Paths
Verte
Path
x
a S→a
b S→a→b
c S→a→c
d S→a→d
Verte
Path
x
S→a→d
e
→e
Order of Visiting Vertices
S → a →d → b →c → e