can someone clear my doubt....

Question

I think Dijkstra algo. works fine with negative weight in connected graphs but not with negative cycle..if we have -ve weight but no cycle then it will give the shortest path ryt??

refer gate 2008 questing...  

Dijkstra gives incorrect result in -ve wt. cycle without detecting

Bellman ford obviously works fine in case of -ve weight and also used to detect the negative cycle..It tells there is -ve wt. cycle and never gives wrong result....????

Answer 1

Dijkstra algo. not always works fine with negative weight in connected graphs.

Here shortest path from $S$ to $A$ is $S-B-A$ but Dijkstra algo. will give $S-A$.

Comments

but sometime it works with -ve weight ryt??

---

yes. May or may not give correct value with negative edges.

Answer 2

When graph contains negative edge weight then dijskta may or may not give correct answer but if it has negative edge weight cycle then it definitely fails

For Bellman Ford it works fine with negative edges but in case of negative edge weight cycle it detects it easily.