Finding the detour-critical edge of a shortest path between two nodes

Let P-G(r, s) denote a shortest path between two nodes r and s in an undirected 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 PG-e(u, s) minus the length of P-G(u, s) is maximum. We call such an edge a detour-critical edge. We will show that this problem can be solved in O(m + n log n) time, where n and in denote the number of nodes and edges in the graph, respectively. (C) 1998 Elsevier Science B.V. All rights reserved.