Find the single-source shortest path using Dijkstra's algorithm

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 single-source 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.

 

****************