Advanced Database Management System - Tutorials and Notes: Find the single-source shortest path using Dijkstra's algorithm
Please visit, subscribe and share 10 Minutes Lectures in Computer Science

Friday, 4 June 2021

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.

 

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

 

 

 

 

 

 

 

No comments:

Post a Comment

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

All time most popular contents