Problem:
Consider a directed graph $ G = (V,E) $ and a source vertex $ s $ with the following properties: edges that leave the source vertex s have arbitrary (possibly negative) lengths; all other edge lengths are non-negative; and there are no edges from any other vertex to the source $ s $. Does Dijkstra's shortest-path algorithm correctly compute shortest-path distances (from $ s $) in this graph?
Solution:
It does correctly compute the shortest-path distance. To claim that, let's go back to the major idea in the proof of correctness.
We argue by the time Dijkstra's algorithm set to shortest path, that path has to be shortest, and we argue that by splitting an arbitrary path from $ s $ to $ t $ into three parts.
$ s \to v $ (where we know $ s \to v $ is an already known shortest path)
$ v \to x $ (where $ x $ is some node that we do not know the shortest path yet), and finally
$ x \to t $ it may or may not be getting back to some nodes with known shortest path.
The key thing that we need from the non-negativity of edge length is that we need to be sure that the path $ x \to t $ has non-negative length, and yes, this is satisfied in our modified problem because $ x $ is the node with unknown shortest path and therefore cannot be $ s $, but all paths with potentially negative edge weight must start with $ s $, so we can still claim $ x \to t $ has non-negative edge weight.
Consider a directed graph $ G = (V,E) $ and a source vertex $ s $ with the following properties: edges that leave the source vertex s have arbitrary (possibly negative) lengths; all other edge lengths are non-negative; and there are no edges from any other vertex to the source $ s $. Does Dijkstra's shortest-path algorithm correctly compute shortest-path distances (from $ s $) in this graph?
It does correctly compute the shortest-path distance. To claim that, let's go back to the major idea in the proof of correctness.
We argue by the time Dijkstra's algorithm set to shortest path, that path has to be shortest, and we argue that by splitting an arbitrary path from $ s $ to $ t $ into three parts.
$ s \to v $ (where we know $ s \to v $ is an already known shortest path)
$ v \to x $ (where $ x $ is some node that we do not know the shortest path yet), and finally
$ x \to t $ it may or may not be getting back to some nodes with known shortest path.
The key thing that we need from the non-negativity of edge length is that we need to be sure that the path $ x \to t $ has non-negative length, and yes, this is satisfied in our modified problem because $ x $ is the node with unknown shortest path and therefore cannot be $ s $, but all paths with potentially negative edge weight must start with $ s $, so we can still claim $ x \to t $ has non-negative edge weight.
No comments:
Post a Comment