0
$\begingroup$

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

enter image description here

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.