Test by Bikram | Algorithms | Test 2 | Question: 28

Question

Assume Dijkstra's Algorithm is used to find the shortest paths from node G in the above graph. The total number of edges which are not included in any of the shortest paths from node G are  _________.

Answer 1

Using Dijikstras algorithm, we will find minimum weight edges which may or may not be adjacent but not forming cycle so that all vertices are visited.

Selecting minimum weight edge is GH(2)---------1

then next minimum weight edge is GJ(3)--------- 2

then next minimum weight edge is JK(4)--------- 3

then next minimum weight edge is IJ(4)--------- 4

Total edges are 8, 4 are visited therefore remaining are 8-4=4 which are GK(5), KI(5), KH(6), HI(7) 

 

Comments

selecting:
              first GH(2)

              second GJ(3)

              third GK(5)

              fourth JI(4)

Answer 2

after applying Dijkastra algo we will find edges j-k ,k-h, k-i and h-i won't be used

hence total 4 edges that is not used