The crucial change in the below implementation is the
addition of the
elif and of the two
lines. (Other changes are to the function parameters and
the addition of the assignment to
source = vertices
for v in vertices: v.dist = INFINITY
source.dist = 0
q = new queue()
while not q.isEmpty():
u = q.remove()
for v in u.neighbors:
if v.dist == INFINITY:
v.dist = u.dist + 1
elif v.dist % 2 == u.dist % 2:
elif condition can be just
v.dist == u.dist”, since when BFS
discovers a previously-discovered vertex, the vertex's distance
will either be at the same distance from the source, or it will
be one link farther from the source.)
We can add each router's delay to all its outgoing edges, and
then we can run Dijkstra's algorithm on that.
We add a new vertex labeled α, which is connected to
each start vertex with a zero-length edge. And we add
a new vertex labeled ω, which is connected to each end vertex
with a zero-length edge. Then we run Dijkstra's algorithm to
find the shortest path from α to ω. The second step
along the shortest path found is guaranteed to be a vertex from the
start set, and the next-to-last step is guaranteed to be a
vertex from the end set. The path found between the second
vertex and the next-to-last vertex is the shortest path from the
start set to the end set.
For each vertex v, we create two copies of the
vertex, v0 and v1, which will be connected
with a directed edge of zero length from
v0 to v1.
For each smooth road from u to v,
we include an edge from u0 to v0
and from u1 to v1.
For each rough road from u to v,
we include a directed edge from
u0 to v1 (and from
v0 to u1 if it is a two-way road).
We then use Dijkstra's algorithm on this new graph to find
the shortest path from
s0 to t1. This path can only use
a single rough road, since taking a rough road takes it from the
v0's to v1's, and after that there
is no way to go back. If the shortest acceptable path takes no rough roads,
then it will take one of the zero-length directed edges from
some v0 to the corresponding v1.
If the graph contains any edges with negative weights, then
Dijkstra's algorithm does not find the correct answer. But
Bellman-Ford does (assuming there are no cycles whose total
weight is negative).