CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithmshortest-path
Iteeeh
Iteeeh

Reputation: 67

algorithm to solve the replacement paths problem for specific situations

I have to solve this problem and it has been bugging me for hours and I can't seem to find a valid solution that satisfies the time complexity required.

For any edge e in any graph G, let G\e denote the graph obtained by deleting e from G.

(a)Suppose we are given an edge-weighted directed graph G in which the shortest path σ from vertex s to vertex t passes through every vertex of G. Describe an algorithm to compute the shortest-path distance from s to t in G\e, for every edge e of G, in O(VlogV) time. Your algorithm should output a set of E shortest-path distances,one for each edge of the input graph. You may assume that all edge weights are non-negative.[Hint: If we delete an edge of the original shortest path, how do the old and new shortest paths overlap?

(b) Describe an algorithm to solve the replacement paths problem for arbitrary undirected graphs in O(V log V ) time.

Upvotes: 0

Views: 1289

Answers (2)

stiar
stiar

Reputation: 368

First of all I want to mention that the complexity can't only depend on V since the output should contain E values, therefore I guess it should be O(E + Vlog(V)).

I think the following idea should work for problem b) and thus for a) as well. Let σ be the shortest s-t path.

  1. For every edge e in G/E(σ), the shortest path in G/e is still σ.
  2. If we remove an edge e in σ, then the shortest path in the remaining graph would like this: it would start going along σ, then would continue outside (might be from the very first vertex s, then go back to σ (might be at the very last vertex t). Let's then iterate over all edges e=(u,v) that either go from G/σ to σ, or from one vertex of σ, that is closer to s, to another vertex of σ, that is closer to t, as edges of potential candidate paths for some shortest s-t path in G/e' for some e'. Suppose that w is the last vertex in the shortest s-u path U that belongs to σ. Then U+e+σ[v..t] is a potential candidate for a shortest s-t path in graphs G/e' for all e' in σ[w..v]. In order to efficiently store this candidate, we can use a Segment Tree data structure with min operation. This would give us O(E log(E)) total complexity for all updates after we consider all edges. It might be possible to make it O(Vlog(V)) if we look closer at the structure of the updates, but I am not sure at the moment, might be not. Precomputing vertices w for each shortest s-u path above can be done in a single Dijkstra run, if we already have σ.

So in the end the solution runs in O(Elog(E)) time. I am not sure how to make it O(E + Vlog(V)), it is possible to make Dijkstra to run in this time by using Fibonacci heap, but for the updates for candidates I don't really see a faster solution at the moment.

Upvotes: 0

amirali
amirali

Reputation: 1964

a) Consider the shortest path P between vertices s and t. Since P is a shortest path, there is no edge between any two vertices u and v in P in which the length of shortest path between u and v is bigger than 1 in the induced graph P. Since every vertex in G is present in P, So every edge of G is present in the induced graph of P. So we conclude that every edge in G is between two adjacent vertices in P (not the induced graph of P). The only thing you should check for each edge e which connects vertices u and v in G, is that there is another edge which connects u and v in G. If so, the shortest path doesn't change in G/e, otherwise s and t will lie on different components.

Upvotes: 2

Related Questions