Finding an anti-risk path between two nodes in undirected graphs
Given a weighted graph G=(V,E) with a source s and a destination t, a traveler has to go from s to t. However, some of the edges may be blocked at certain times, and the traveler only observes that upon reaching an adjacent site of the blocked edge. Let a"similar to={P (G) (s,t)} be the set of all paths from s to t. The risk of a path is defined as the longest travel under the assumption that any edge of the path may be blocked. The paper will propose the Anti-risk Path Problem of finding a path P (G) (s,t) in a"similar to such that it has minimum risk. We will show that this problem can be solved in O(mn+n (2)log n) time suppose that at most one edge may be blocked, where n and m denote the number of vertices and edges in G, respectively.
anti-risk path shortest path shortest path tree most vital real time edge