retagged by
1,482 views
1 votes
1 votes

I think answer should be Option(B).

Path:<s,y><y,x><x,t> = 7-3-2=2

retagged by

3 Answers

Best answer
4 votes
4 votes

According to dijkstra's algorithm, we will get shortest path as 6 which is a direct edge from s -> t.

There are only two direct edge from s  i.e  s -> t  with weight  6  and  s ->y  with weight 7 ,out of which 6 is minimum.

So, it will be selected in the first iteration itself.

Hence, Answer is 6

Note:- But manually if we calculate,we can get the shortest path as 2. So, we can consider this example to show that why dijkstra algorithm fails for the negative weighted edges.

selected by

Related questions

2 votes
2 votes
1 answer
3
Sahil Gupta asked Dec 16, 2014
643 views
if Dijkstra shorest path algorithm takes 8 second for a graph of 1000 nodes then approximatly how much time would it take for a graph of 1000000 nodes.a) 8000000 sec.b) 8...
–1 votes
–1 votes
1 answer
4