GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
99 views

Apply single source shortest path algorithm on the given graph using vertex ‘A’ as the source. What is the maximum possible distance between vertex A to vertex G. (Assume exclude infinity).

Ans is 28.

asked in Algorithms by Boss (6.1k points)   | 99 views

1 Answer

+5 votes
Best answer
Queue B C D E F G H  
{ A } 4 5 Select B
{ A,B } - 5 15 Select C
{ A,B,C } - - 15 15 11 select F
{ A,B,C,F } - - 15 15 - 28 12 select H
{ A,B,C,F,H } - - 15 15 - 24 - select D
{ A,B,C,F,H,D } - - - 15 - 24 - select E
{ A,B,C,F,H,D,E } - - - - - 24 - select G

From above table we found that the max distance to reach G is possible by applying single shortest path algorithm costs 28

 

answered by Boss (7.8k points)  
selected by
i got 28 via F

24 via H

30 via E ..

do the math again .would you? and correct me
we have to apply SSSP algo


Top Users Aug 2017
  1. ABKUNDAN

    4660 Points

  2. Bikram

    4366 Points

  3. akash.dinkar12

    3258 Points

  4. rahul sharma 5

    3042 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2410 Points

  7. just_bhavana

    2100 Points

  8. Tesla!

    1918 Points

  9. stblue

    1682 Points

  10. joshi_nitish

    1608 Points


24,928 questions
32,024 answers
74,385 comments
30,113 users