## TOPICS (Click to Navigate)

Please visit, subscribe and share 10 Minutes Lectures in Computer Science

# 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.

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

## Featured Content

### Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...