GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
77 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 (6k points)   | 77 views

1 Answer

+4 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.7k 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

Related questions

0 votes
0 answers
1
asked in Algorithms by Vignesh Kamath (287 points)   | 113 views
0 votes
2 answers
2
0 votes
2 answers
3
asked in Algorithms by vaishali jhalani Boss (6k points)   | 146 views


Top Users Mar 2017
  1. rude

    4018 Points

  2. sh!va

    2994 Points

  3. Rahul Jain25

    2804 Points

  4. Kapil

    2608 Points

  5. Debashish Deka

    2104 Points

  6. 2018

    1414 Points

  7. Vignesh Sekar

    1336 Points

  8. Bikram

    1218 Points

  9. Akriti sood

    1186 Points

  10. Sanjay Sharma

    1016 Points

Monthly Topper: Rs. 500 gift card

21,446 questions
26,757 answers
60,937 comments
22,954 users