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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom