# Find shortest path

1 vote
1k views

retagged
2

B is answer. Go onece for dynamic approch .

Short cut Go with End vertex to start vertex with minmum cost every time .

You get B as answer.

1
or try all options
0
A and B seems to be having smae cost, so is one preferable to another?
3
BUT WHAT IS THE EDGE WEIGHT OF EDGE 5-8

seen none are asking about it .Isnt that important?
1
Bt removing edge 5-8

and applying D.A.

1-2-4-8-9

cost=15

## 3 Answers

3 votes
This is not a multi-stage graph since, in a multistage graph, edges can only be present between stage i and stage (i+1). Here, we have an edge from 1 to 5 i.e. stage 1 to stage 3 which is not correct.
0
Point to be noted... So in this case what should be the answer???
0
same doubt why we are applying dynamic approach here?
0

Because Dijkstra Algorithm takes O(E log V )time.

And Using Dynamic Programming time complexity = O($V^{2}$) = O(E)

2 votes

Option B

Multi stage graph if we follow greedy strategy answer will not always be optimum . Dynamic Approch is prefered here .

Like @anirudh said  for short-cut

Start  with End vertex and traverse to  start vertex with minmum cost every time

For General Approch . Watch this (https://www.youtube.com/watch?v=m5Y-4TsXsJ0)

Good Read

0
Apply Dijkstra Algorithm answer  will be B.if u apply hit and trial method u may get correct answer but the approach is wrong
0
@Pc, can we apply Dijakstra algorithm here?
0
@rahul_sharma_5 , read that ref (final analysis ) , it will make more clarity
2 votes
In this A and B both are havinng same cost, but if we follow greedy approach it will not give A as answer as till it ll not get less cost it will use previous only and from dynamic both answers are correct so B should be the answer.

In multistage we start from end vertex not from starting vertex if we start from starting vertex then A should be the answer but according to  multistage algo B should be the answer.
2
When I am calculating, the answer is turning out to be

1-->2-->4-->8-->9

Sum= 14

Shouldn't this be the accurate answer?
0
I too got the same result. Yes it's correct

## Related questions

5 votes
7 answers
1
1k views
Acc. to dijkstra's algorithm: What will be the shortest path from A to B ? 1) When the edge of length 15 is present. 2) when the edge of length 15 is removed.
3 votes
2 answers
2
457 views
Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a shortest path from s to t. T/F
1 vote
1 answer
3
298 views
Read the following statements below For all the below questions consider the graph as simple and has positive weight edges. (i) Let the cost of the shortest path between two nodes is S.If the weight of every edge in the graph is doubled then weight of the shortest ... iii) We can use Kruskal's algorithm to find Minimum spanning tree of a directed graph . How many of the above statements are true.
1 vote
3 answers
4
351 views
For a given undirected weighted graph G with V number of vertices, if you want to find all pair shortest paths then which one of the following is true ? a) run dijkstra's shortest path algorithm only once. b) run dijkstra's shortest path algorithm V times. What if the given graph is directed ?