Data Structures, Algorithms, & Applications in C++
Chapter 17, Exercise 31
When the edge weights are >= 0, there is always a next shortest
path that is a one edge extension of an already generated shortest path
provided there is a next shortest path.
Suppose the next shortest path P from
vertex s is to vertex v.
Let u be the last vertex
on this path such that we have already generated
a shortest path to
u.
If u immediately precedes
v on
P, then the next shortest path is
a one-edge extension of an already generated path.
If u does not immediately precede
v on
P, then the length of the
subpath of P from
u to
v must be zero because otherwise,
the length of the subpath of
P from s
to u is shorter than the length of
P. Therefore,
P cannot be the next shortest path.
Since the length of the subpath to u
is the same as the length of the next shortest path, we can
generate the shortest path to u next
instead of the path to v. Therefore,
there is a next shortest path which a one-edge extension
of an already generated shortest path.