The next‐to‐shortest path problem on directed graphs with positive edge weights
Bang Ye Wu, Hung‐Lung Wang · Networks · 2015
Given an edge‐weighted graph G and two distinct vertices s and t of G, the next‐to‐shortest path problem asks for a path from s to t of minimum length among all paths from s to t except the shortest ones. In this article, we consider the version where G is directed and all edge weights are positive. Some properties of the requested path are derived when G is an arbitrary digraph. In addition, if G is planar, an ‐time algorithm is proposed, where n is the number of vertices of G. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(3), 205–211 2015