Problem:
Consider a directed graph $ G = (V,E) $ with non-negative edge lengths and two distinct vertices $ s $ and $ t $ of $ V $. Let $ P $ denote a shortest path from $ s $ to $ t $ in $ G $. If we add 10 to the length of every edge in the graph, then:
Solution:
Let consider this graph:
s -1-> a
a -1-> t
s -3-> t
The current shortest path is s -1-> a -1-> t has cost 2.
Suppose we add 10 to each edges, the path is no longer optimal, the optimal path will become
s -13-> t
The general transformation of path cost is path cost + number of edges times 10, therefore, path with less number of edge will be proportionally shorten than the one with larger number of edges, the construction of the example above is based on this.
Therefore we can consider the choices now:
(Option 1) $ P $ definitely remains a shortest $ s - t $ path.
This is obviously wrong given the example above.
(Option 2) $ P $ might or might not remain a shortest $ s − t $path (depending on the graph).
This is true, the example above shown this could be not the shortest path. It could be the shortest path, for example, in case there is only one path.
(Option 3) $ P $ definitely does not remain a shortest $ s - t $ path.
This is obviously wrong given the above.
(Option 4) If $ P $ has only one edge, then $ P $ definitely remains a shortest $ s − t $ path.
This is true, but it is non-obvious. This can be proved by looking at the cost transformation.
Suppose the contrary that there exists another path $ Q $ after the transformation is shorter than $ P $, then
New Cost of Q < New Cost of P
Old Cost of Q + num edges in Q times 10 < Old Cost of P + 10
Now num edges in Q must be at least 1, so we have
Old Cost of Q + 10 < Old Cost of P + 10
Old Cost of Q < Old Cost of P
But that is impossible! $ P $ was the shortest path!
Therefore we proved option 4 is true.
Consider a directed graph $ G = (V,E) $ with non-negative edge lengths and two distinct vertices $ s $ and $ t $ of $ V $. Let $ P $ denote a shortest path from $ s $ to $ t $ in $ G $. If we add 10 to the length of every edge in the graph, then:
Solution:
Let consider this graph:
s -1-> a
a -1-> t
s -3-> t
The current shortest path is s -1-> a -1-> t has cost 2.
Suppose we add 10 to each edges, the path is no longer optimal, the optimal path will become
s -13-> t
The general transformation of path cost is path cost + number of edges times 10, therefore, path with less number of edge will be proportionally shorten than the one with larger number of edges, the construction of the example above is based on this.
Therefore we can consider the choices now:
(Option 1) $ P $ definitely remains a shortest $ s - t $ path.
This is obviously wrong given the example above.
(Option 2) $ P $ might or might not remain a shortest $ s − t $path (depending on the graph).
This is true, the example above shown this could be not the shortest path. It could be the shortest path, for example, in case there is only one path.
(Option 3) $ P $ definitely does not remain a shortest $ s - t $ path.
This is obviously wrong given the above.
(Option 4) If $ P $ has only one edge, then $ P $ definitely remains a shortest $ s − t $ path.
This is true, but it is non-obvious. This can be proved by looking at the cost transformation.
Suppose the contrary that there exists another path $ Q $ after the transformation is shorter than $ P $, then
New Cost of Q < New Cost of P
Old Cost of Q + num edges in Q times 10 < Old Cost of P + 10
Now num edges in Q must be at least 1, so we have
Old Cost of Q + 10 < Old Cost of P + 10
Old Cost of Q < Old Cost of P
But that is impossible! $ P $ was the shortest path!
Therefore we proved option 4 is true.
No comments:
Post a Comment