Review 4: Paths in graphs: Questions
Recall the breadth-first search algorithm.
def bfs(vertices, source):
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)
A graph is said to be bipartite if the vertices can be divided into two groups, and every edge connects one group to another. Assuming we're given a graph where all vertices are reachable from each other, how can we modify our breath-first search code in order to determine whether our graph is bipartite?
We can model a data network as a directed graph, with each vertex corresponding to a router and each edge corresponding to a connection between routers. In routing data through a network, there is a time delay associated with going through a connection — but there is also a time delay associated with passing through the router from one connection to the next. How can we use Dijkstra's algorithm so that it still finds the fastest route between two points in the network?
Suppose we have a weighted, undirected graph where all weights are positive. Two sets of vertices have been identified: One is a collection of possible start points, and the other is a collection of possible end points. Each set has √n vertices. We want to find the shortest path from any single vertex in the start set to any vertex in the end set.
Give an O(m log n)-time algorithm for solving this problem. (Recall that Dijkstra's algorithm takes O(m log n) time, but it works only from a single source to a single destination.)
Suppose we have a network of roads, where each road connects two vertices and has an associated length. However, some of the roads are known to be very rough, and we never want to take a route that takes more than a single rough road. How can we efficiently find the shortest route between two points s and t that doesn't traverse more than a single rough road?
Why use the Bellman-Ford algorithm for finding the shortest path between two vertices in a graph, when Dijkstra's algorithm does the same thing and is faster?
Review 4: Paths in graphs: Solutions
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, 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).