GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
83 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)   | 83 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 Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,088 questions
28,063 answers
63,298 comments
24,173 users