The next-to-shortest path problem on directed graphs with positive edge weights

Bang Ye Wu; Hung Lung Wang

doi:10.1002/net.21598

The next-to-shortest path problem on directed graphs with positive edge weights

Bang Ye Wu
, Hung Lung Wang^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

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 (n 3)-time algorithm is proposed, where n is the number of vertices of G.

Original language	English
Pages (from-to)	205-211
Number of pages	7
Journal	Networks
Volume	65
Issue number	3
DOIs	https://doi.org/10.1002/net.21598
Publication status	Published - 2015 May 1
Externally published	Yes

Keywords

algorithm
digraph
directed acyclic graph
k shortest paths
next-to-shortest path
planar graph
time complexity

ASJC Scopus subject areas

Information Systems
Computer Networks and Communications

Access to Document

10.1002/net.21598

Cite this

@article{16198759eb4f42e8b13d0c07fe061432,

title = "The next-to-shortest path problem on directed graphs with positive edge weights",

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 (n 3)-time algorithm is proposed, where n is the number of vertices of G.",

keywords = "algorithm, digraph, directed acyclic graph, k shortest paths, next-to-shortest path, planar graph, time complexity",

author = "Wu, \{Bang Ye\} and Wang, \{Hung Lung\}",

note = "Publisher Copyright: {\textcopyright} 2015 Wiley Periodicals, Inc.",

year = "2015",

month = may,

day = "1",

doi = "10.1002/net.21598",

language = "English",

volume = "65",

pages = "205--211",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - The next-to-shortest path problem on directed graphs with positive edge weights

AU - Wu, Bang Ye

AU - Wang, Hung Lung

PY - 2015/5/1

Y1 - 2015/5/1

N2 - 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.

AB - 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.

KW - algorithm

KW - digraph

KW - directed acyclic graph

KW - k shortest paths

KW - next-to-shortest path

KW - planar graph

KW - time complexity

UR - https://www.scopus.com/pages/publications/84926520690

UR - https://www.scopus.com/pages/publications/84926520690#tab=citedBy

U2 - 10.1002/net.21598

DO - 10.1002/net.21598

M3 - Article

AN - SCOPUS:84926520690

SN - 0028-3045

VL - 65

SP - 205

EP - 211

JO - Networks

JF - Networks

IS - 3

ER -

The next-to-shortest path problem on directed graphs with positive edge weights

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this