Publisher： John Wiley & Sons Inc
E-ISSN： 1097-0037|65|3|205-211
ISSN： 0028-3045
Source： NETWORKS: AN INTERNATIONAL JOURNAL, Vol.65, Iss.3, 2015-05, pp. : 205-211
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
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 O(n3)‐time algorithm is proposed, where n is the number of vertices of G. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(3), 205–211 2015
Related content
Access to resources
Recommend
A shortest path problem on a network with fuzzy arc lengths
Fuzzy Sets and Systems, Vol. 109, Iss. 1, 2000-01 ,pp. :
An Incremental Algorithm for a Generalization of the Shortest-Path Problem
Journal of Algorithms, Vol. 21, Iss. 2, 1996-09 ,pp. :
Edge Weight Reduction Problems in Directed Acyclic Graphs
Journal of Algorithms, Vol. 24, Iss. 1, 1997-07 ,pp. :