Dijkstra's algorithm in data structures, single source shortest path algorithm solved exercise
Question: Consider the given undirected weighted graph. Use Dijkstra’s algorithm to calculate the singlesource shortest paths from A to every other vertex.
Solution:
Vertex 
Known 
Cost from source A 
Minimum cost to reach next vertex 
Next vertex chosen 
Visited vertices 
A (source) 
Y 
0 

 
A 
From A, we can go to either B, or C, or F 


B 
Y 
1 
Choose next vertex as follows; minimum(AB, AC, AF) = min(1, 3, 10) = 1 Choose B (cost = 1) as the next vertex. 
B 
AB 
C 
Y 
3 

F 
Y 
10 

Vertices visited 

From B, we can go to C, D, E, or G and from A we can reach C directly 

C 
Y 
AB+BC = 1+1 = 2 
Min(ABC, ABD, ABE, ABG, AC) = min(2, 8, 6, 3, 3) = 2 Choose C (cost = 2) as the next vertex. 
C 
ABC 
D 
Y 
AB+BD = 1+7 = 8 

E 
Y 
AB+BE = 1+5 = 6 

G 
Y 
AB + BG = 1+2 = 3 

C 
Y 
AC = 3 

Vertices visited 

From C, we can reach D or E and from B we can reach G 

D 
Y 
ABC+CD = 2+9 = 11 
Min(ABCD, ABCE, ABG) = min(11, 5, 3) = 3 Choose G (cost = 3) as the next vertex. 
G 
ABCG 
E 
Y 
ABC+CE = 2+3 = 5 

G 
Y 
AB+BG = 1+2 = 3 

Vertices visited 

From G, we can go to D and from C we can go to D or E 

D 
Y 
ABG+GD = 3+12 = 15 
Min(ABGD, ABCE, ABCD) = min(15, 5, 11) = 5 Choose E (cost = 5) as the next vertex. 
E 
ABCEG 
E 
Y 
ABC+CE = 2+3 = 5 

D 
Y 
ABC+CD = 2+9 = 11 



Vertices visited 

Next we can reach D or F 

D 
Y 
ABG+GD = 3+12 = 15 
Min(ABGD, ABD, ABCED, ABCD, ABCEF, AF) = min(15, 8, 7, 11, 7, 10) = 7
Choose D or F (cost = 7) as the next vertex.
After D, we can choose F (cost = 7) as the next vertex. 
D F 
ABCDEFG 
D 
Y 
AB+BD = 1+7 = 8 

D 
Y 
ABCE+ED = 5+2 = 7 

D 
Y 
ABC+CD = 2+9 = 11 

F 
Y 
ABCE+EF = 5+2 = 7 

F 
Y 
AF = 10 
The shortest path will be;
From this graph, we can get the shortest path from single source (A in this case) to any other vertices. For instance, the shortest path from A to D is ABCED with the cost 7 (AB+BC+CE+ED). The shortest path from A to G is ABG with the cost 3 (AB+BG). The shortest path from A to C is ABC with the cost 2 (AB+BC) etc.
****************
No comments:
Post a Comment