Review 4: Paths in graphs

The crucial change in the below implementation is the addition of the elif and of the two return lines. (Other changes are to the function parameters and the addition of the assignment to source.)

def is_bipartite(vertices):
    source = vertices[0]
    for v in vertices: v.dist = INFINITY
    source.dist = 0

    q = new queue()
    q.add(source)
    while not q.isEmpty():
        u = q.remove()
        for v in u.neighbors:
            if v.dist == INFINITY:
                v.dist = u.dist + 1
                q.add(v)
            elif v.dist % 2 == u.dist % 2:
                return False
    return True</b>

(Actually, the 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, v₀ and v₁, which will be connected with a directed edge of zero length from v₀ to v₁. For each smooth road from u to v, we include an edge from u₀ to v₀ and from u₁ to v₁. For each rough road from u to v, we include a directed edge from u₀ to v₁ (and from v₀ to u₁ if it is a two-way road).

We then use Dijkstra's algorithm on this new graph to find the shortest path from s₀ to t₁. This path can only use a single rough road, since taking a rough road takes it from the v₀'s to v₁'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 v₀ to the corresponding v₁.

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).