Premium
The next‐to‐shortest path problem on directed graphs with positive edge weights
Author(s) -
Wu Bang Ye,
Wang HungLung
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21598
Subject(s) - digraph , combinatorics , shortest path problem , longest path problem , mathematics , directed graph , path (computing) , distance , enhanced data rates for gsm evolution , induced path , graph , discrete mathematics , computer science , artificial intelligence , programming language
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 ( n 3 ) ‐time algorithm is proposed, where n is the number of vertices of G . © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(3), 205–211 2015