Dijkstra Algorithm

Question

I think answer should be Option(B).

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

Comments

Answer is option A

S->t = 6

---

@Ashwin,

though correct shortest dist(S,T) = 2,  but dijikstra's algorithm will mark dist(S,T) = 6

option A) is correct

---

How is it 6?

---

I think I've applied Bellman ford.

So @joshi_nitish

s-t = 6

s-x = 11

s-y = 7

s- z = 2

Is it correct in Dijakstra?

---

s-x = 4, rest all are correct.

---

Yes got that thanks. I was just confused.

---

Dijkstra is a Greedy Algorithm, so it will choose minimum among all present in heap and delete it. so after deleting s with value 0 which is a starting vertex, next minimum will be t with value 6 and that will be shortest path according to Dijkstra's algorithm.

So according to Dijkstra's algorithm. = 6

But actually it should be 2.

---

Dijkstra’s algorithm doesn’t work for graphs with negative weight edges. For graphs with negative weight edges, Bellman-Ford algorithm can be used. But Bellman-Ford also failed, in the Negative Weight Cycle.

So,how Shortest Path $S\rightarrow T=6?$

and If I want to find the Shortest Path $S\rightarrow Z=?$

---

DIJKSTRA'S algorithms does not work for graphs  if a graph containing negative weight edge cycles

---

Dijkstra’s algorithm doesn't have the capacity to detect the negative weight cycle. I learn from the geeks for geeks, it says it does not work, even negative weight edge.

see this https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

Notes:5) Dijkstra’s algorithm doesn’t work for graphs with negative weight edges. For graphs with negative weight edges, Bellman-Ford algorithm can be used, 

---

@ suneetha

I want to find the Shortest Path S→Z=?

what is the answer?

---

@Lakshman Patel RJIT

Bro,  Who told you Dijkastra does not Work for negative weight  ???

Dijkstra works for Negative weight But There should not be the Negative Weight Cycle in the Graph. And Also It Does not Detect the Cycle That's Why we use Bellmen-Ford Algo to detect the Cycle. If the Cycle exist Then Bellmen Ford Will Also Be Failed.

 

---

@ kumar.dilip

see this  https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

---

@ kumar.dilip

In this question, where is Negative Weight cycle, why an answer is $6$, why not$2$?

---

i think dijkstr's algorithm is not applied for this question because t->x and x->t negative weight edge cycle is present and also

y->z z->x x->t t->y there is also  negative weight edge cycle is present so dijkstra's algorithms is not applicable for this graph?

ans may be wrong

---

In given question where is negative weight cycle?

---

Dijkastra Algo does not work for Negative Weight Cycle.But we can Apply It on Negative Weight(No cycle), It will give you the correct answer.

you can take any Example Without Negative Weight Cycle you will find the correct answer.

You can check it.

---

@Lakshman Patel RJIT

Please tell.

Why Dijkastra can't Detect Cycle ???

If give the answer of this question Then your Doubt will be clear.

---

Why Dijkastra Algo is not able to find the shortest path?

 

---

in your question there is no negative weight edge cycle so

the shortest distance from s to a is 5 and

the shortest distance from s to b is s->a + a->b = 5+(-2)=3

---

@kumar.dilip 

Why Dijkastra can't Detect Cycle ???

Because of it relax at a time only neighbor edge not all edges 

---

negative weight edge cycle means the cycles which is containing at least one negative weight edge

---

In this question, where is Negative Weight cycle, why an answer is 6, why not2?

Lakshman Patel RJIT

we can implement the dijkstra's algorithms using min heap..

So we always relaxing all the edges from from the min node then we  perform delete min operation  and  again relaxing the edges of the min node and the process is continue until our heap is empty .

So when we relation all the edges of node "t"

we delete that node..so node t is not present in the graph now...therefore we can't change it's value to (-2) first of all

 

2nd  dijkstra's algorithms   sometimes given incorrect result when there is  a  negative edges and It also Does not Detect the Cycle 

I want to find the Shortest Path S→Z=?

 

16 

---

@Magma

nice explanation.

---

@Magma

can you check this

 

---

yeah correct

I did mistake ....that time

---

Thanks, Brother, you clear my doubts.

Answer 1

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.

Comments

You have to relax all the edges can you please check it once again.
@arjun sir can you help with this.

---

@Arpit

What you mean by relaxing the edges?

---

https://stackoverflow.com/questions/12782431/relaxation-of-an-edge-in-dijkstras-algorithm

Answer 2

A(6) will be answer.

Answer 3

It will be 2 in Bellman Ford but correct in 6 THrough Dijkastra algorithm