Dijkstra’s algorithm, commonly used to find the path of minimum weight to any given node from a starting node in a weighted graph, does not work if negative weights are allowed.

Intuitively, the reason is that Dijkstra’s makes the assumption while working through the graph that paths can only become ‘heavier’, and so while visiting a node does not consider neighbors which themselves have already been visited. For instance, consider running the algorithm on the following graph with **A** as the starting node:

Image: https://stackoverflow.com/q/13159337

The algorithm will look at **C **as a neighbor of **A** and set its minimum known distance to 2. It will then look at **B** and set its to 5. It will then move on to visit **C** without any changes since **C** has no neighbors. It will then visit **B**, but will not consider the edge from **B **to **C** because **C** has already been visited. So the algorithm will wrongly conclude that the shortest path to **C** from **A** is 2, not -5.

One adaptation which does work on certain types of graphs with negative weights is *Johnson’s algorithm*, which itself uses Dijkstra’s as a subroutine.

## Recent Comments