FINDING THE DETOUR-CRITICAL EDGE OF A SHORTEST-PATH BETWEEN 2 NODES

Let P-G(r, s) denote a shortest path between two nodes r and s in an u ndirected graph G with nonnegative edge weights. A detour at a node u epsilon P-G(r, s) = (r,..., u, v,...,s) is defined as a shortest path PG-e(u,s) from u to s which does not make use of (u, v). In this paper we focus on the problem of finding an edge e = (u, v) epsilon P-G(r, s) whose removal produces a detour at node u such that the length of P G-e(u, s) minus the length of P-G(u, s) is maximum. We call such an ed ge a detour-critical edge. We will show that this problem can be solve d in O(m + n log n) time, where n and in denote the number of nodes an d edges in the graph, respectively. (C) 1998 Elsevier Science B.V. All rights reserved.