Dijkstra Algorithm

@Ashwin,

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

option A) is correct

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$?

@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?

@kumar.dilip 

Why Dijkastra can't Detect Cycle ???

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

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