Faster algorithm to find anti-risk path between two nodes of an undirected graph

摘要

For a weighted 2-edge connected graph G = (V,E), we are to find a “minimum risk path” from source s to destination t. This is a shortest s ?t path under the assumption that at most one edge on the path may be blocked. The fact that the edge is blocked is known only when we reach a site adjacent to the blocked edge. If n and m are the number of nodes and edges of G, then we show that this problem can be solved in O(n~2) time using only simple data structures. This is an improvement over the previous O(mn + n~2 log n) time algorithm. Moreover, with use of more complicated data structures like Fibonacci Heaps and transmuters the time can be further reduced to O(m+ n log n).