Skip to main content
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Source Link
RajS
  • 1.7k
  • 5
  • 28
  • 48

Negative edge weights in Dijkstra and Bellman Ford shortest path algorithms

The main difference between Dijkstra algorithm and Bellman Ford algorithm that all texts (including CLRS) specify is that Dijkstra's algorithm need all non negative edge weights, while Bellman Ford algorithm can work with and detect -negative edge cycles.

However I feel a bit different, especially after coming across problem asking to build shortest path tree from node $a$ in following graph:

enter image description here

My shortest path tree after running Dijkstra came like this:

enter image description here

Then why texts say that Dijkstra need all non negative edge weights? I feel that it should be no -ve edge weight cycle reachable from source node. Am I correct with this? or am I missing something here?