The most important edge on the fast track

Question

I have this question from the Sedgewick course on algorithms: “ Critical edge . For a digraph bound to the edge, create the E*log(V) algorithm to find an edge whose removal leads to the maximum increase (possibly infinitely) along the shortest path from s to t . Assume that all the weights of the edges are strictly positive. (Hint: calculate the shortest distances of the path d(v) from s to v and consider the cost reduction c′(v,w)=c(v,w)+d(v)−d(w) ≥ 0 ) "

I read on the Internet that three (3) guys in 1989 came up with the O(E + V*log(V)) complexity algorithm, which requires advanced data structures, and I think it was on a graph (not a digraph). If he has three advanced computer scientists to develop these algorithms, isn't that a big deal for an introductory course? But perhaps this is much simpler for O(E*log(V)) .

Can you help me solve this problem? I do not understand the hint given in the question.

Answer 1

This is a confusing question, I agree. Here are some of my thoughts on this.

The term "reduced cost" and the definition are used to reduce the A * search algorithm to Dijkstra's algorithm, replacing the original cost with a reduced cost:

c′(v,w) = c(v,w) - h(v) + h(w) = c(v,w) - (h(v) - h(w)) > 0

Part h(v) - h(w) is a drop of a heuristic function, which should not exceed the cost of the edge in the case of a coordinated (monotonous) heuristic, so the reduced cost is even more than 0 (see slides 14 and 15 here )

It seems that Sedgewick suggests using the original distance function ( d(v) ) as a consistent heuristic when searching for a new / replacement shortest path in G' that matches the original G , but with one remote edge along the original shortest path from s to t . Personally, I don’t understand how this could help solve the most important edge problem in O(ElogV) , though.

There is also a similar problem: find all the curves up and down the curves in the graph. By definition, lowering the cost of the critical edge down reduces the overall cost of SP. Increasing the cost of the rising critical edge increases the total cost of the SP. All critical edges can be found in O(ElogV) , see Ch.8 here . But this does not answer the question of which edge is the most critical (causes an increase in maximum SP when removed).

As you noted, the most important regional problem was solved by Malik, Mittal and Gupta (1989) in O(E + V*log(V)) time. I did not find the original MMG paper, but this presentation explains it pretty well. As far as I can tell, it can be solved using a priority queue, without requiring any specific data structures.

Sorry to not really answer the original question (a solution for the most important edge on the digraph using reduced costs), but still hoping that the links and thoughts above might be useful to someone. I would be glad to see that the solution means Sedgewick.

Answer 2

Here's a sketch of an algorithm to find the critical edge on the shortest path based on the Sedgewick tooltip.

Firstly, the reduced cost c '(v, w) = c (v, w) + d (v) -d (w) corresponds to an increase in the shortest path length from s to w when passing v immediately before w . (If v is in the shortest path from s to w , then this increase is 0.) (Indeed, d (v) is the length of the shortest path from s to v and c (v, w) is the cost of switching from v to w.)

Suppose that the shortest path from s to t is (s, ..., v, t) and that we remove the last edge (v, t) . Then increasing the length of the shortest path from s to t is equal to the minimum c '(u, t) for all in -edges (u, t) , with u! = V.

Suppose that u is such that c '(u, t) is minimal (still u! = V ). Then follow the shortest path from s to u back until you reach a vertex, say w , belonging to the shortest path from s to t (without any remote edge). The shortest path from s to t is something like (s, ..., w, ..., v, t).

Note that if you remove any edge between w and t , you will get the maximum increase c '(u, t) int the shortest path. Indeed, if one of the edges between w and t is missing, it suffices to go from w to t through the vertex u . On the other hand, note that removing the last edge (v, t) will lead to just this increase.

Now just repeat with w , which was done with t . Find the vertex x so that c '(x, w) is mininum and x is not on the shortest path. Follow the shortest path from s to x backward until you reach a vertex belonging to the shortest path from s to w .

Once you reach s , you can determine which vertex to remove to cause the maximum increase in the length of the shortest path.