Dijkstra's

Question

I know that Dijkstra's Doesn't work for Negative weight cycle because it form a loop, Does it also true that it may or may not work for negative weight edge(without cycle) ?

If it is not working for a negative weight edge(without cycle) give some example to prove it.

Comments

DIjikstra's always fails for negative weight cycle reachable from source, but it may or may not fail for negative weight edges(without cycle)

---

Can you provide any example where it is failing with negative edge(no cycle). /\

---

here in above graph, there is no -ve wght cycle, but there is -ve wght edge.

now if you Apply Dijikstra with A as source then the min(A-->B) = 2, but actually minimum dist from A--->B=1

---

Dijkstra's algo is greedy algorithm means it would tell you the shortest path to other vertices in greedy approach.

like let suppose you want the shortest path from some source A to it's directly connected vertices, now as it's greedy it would just tell you that the shortest path to directly connected nodes is the weight of edges b/w those directly connected nodes and source , which is even true if edge weights are positive. But if edge weights are negative then it may happen that through some another edge you get minimum weight to directly connected nodes..

like A to B,C are directly connected with weights 6,9. but from C too you are reaching B (Let BC edge weight = -7) then dijkstra's algo won't be able to tell you the correct shortest path from A to B as once it relaxes some vertex , it never comes back , never(because it's greedy , never reconsider choices). so here it's failing but what if BC edge weight=-1 then there won't be any flaw in dijkstra's algo as still 6< 9-1.