edited by
341 views
2 votes
2 votes

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

edited by

2 Answers

Best answer
1 votes
1 votes

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) 

 

selected by
1 votes
1 votes
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
Answer:

Related questions

1 votes
1 votes
2 answers
2
Bikram asked May 26, 2017
454 views
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.
0 votes
0 votes
1 answer
3
Bikram asked May 26, 2017
303 views
Consider the following instance of the knapsack problem :$\begin{array}{|c|c|c|c|c|c|} \hline \text{Item} & a & b & c & d & e \\ \hline \text{Benefit} & 15 & 12 & 9 & 16 ...
0 votes
0 votes
1 answer
4
Bikram asked May 26, 2017
284 views
Let $T$ be a rooted ternary tree where each internal node of $T$ has a maximum of $3$ children. If root is at depth $0$, then maximum total number of vertices $T$ can hav...