# Running Dijkstra on particular graph with negative weight

After running Dijkstra on this graph from S, which shortest paths will be incorrect?

This graph has a negative weight, so which shortest paths will be incorrect? after my first attempt I got that Y and Z have wrong shortest paths, but that's not true. Can anyone explain why?

## 1 Answer

The shortest path tree of Dijkstra will set root as $$S$$ then it first selects the $$Y$$ with weight 8. Then it will look at the shortest distance of all the neighbor's of the tree. There will be two candidates $$X$$ and $$Z$$. It will choose $$X$$ since the distance is 10. Then finally, it will choose $$Z$$ with distance 11.

The Dijkstra's, as stated, cannot work correctly on graphs with negative weights.

The problem is that it is a greedy algorithm and once it finds the shortest path for a node it is not re-evaluating for any other possibilities may occur in the future. This is not possible if the graph has not negative weights.