Question

Give an efficient algorithm that takes a directed graph G = (V, E) and two vertices u, v E V, and determines if there are at least two edge-disjoint paths in G from u to v. i.e., your algorithm should determine whether there are at least two paths from u to v in G that have no edges in common. Argue your algorithm's correctness and analyze its time complexity.

Answer 1

Solution 1 verse all edges and use Dijkstra to find the shortest paths from all vertices to t. Denote the shortest path from u to v by u, and its length by o(u, v) Now, try setting each edge to zero. For each edge (u, v) E E, consider the path s u ->v t. If we set w(u, v) to zero, the path length is 6(s, u) o(v, t). Find the edge for which this length is minimized and set it to zero; the corresponding path Use Dijkstra's algorithm to find the shortest paths from s to all other vertices. Re- t is the desired path 8u The algorithm requires two invocations of Dijkstra, and an additional e(E) time to iterate through the edges and find the optimal edge to take for free. Thus the total running time is the same as that of Dijkstra: (E+ V lg V) Solution 2: Construct a new graph G' as follows: for each vertex v E V, create two vertices, vo and v, in G'. The vo vertices represent being at v in G and having not yet used the Star. The v vertices represent being at v, and having already used the Star For each edge (u, v) E E, create three edges in G': (uo, vo) and (u1, v1) with the original weight w(u, v), and (uo, v1) with a weight of zero. An edge, (uo, v1), crossing from the "0" component to the "1" component of the graph represents using the Star to traverse (u, v) Now, run Dijkstra's algorithm with source s0 and destination t. Drop the subscripts from the resulting path to recover the desired answer. (Observe that, because all edge weights are positive, it is always optimal to use the Star somewhere.) G' has 2V vertices and 3E edges. Thus, constructing G' takes e(VE) time, and running Dijkstra on G' takes (E V lg V) time. Thus the total running time is e(E V lg V)