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^*

^*此作品的通信作者

研究成果: 雜誌貢獻 › 期刊論文 › 同行評審

3 引文斯高帕斯（Scopus）

摘要

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.

原文	英語
頁（從 - 到）	205-211
頁數	7
期刊	Networks
卷	65
發行號	3
DOIs	https://doi.org/10.1002/net.21598
出版狀態	已發佈 - 2015 5月 1
對外發佈	是

ASJC Scopus subject areas

資訊系統
電腦網路與通信

存取文件

10.1002/net.21598

其它文件與鏈接

引用此

@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

摘要

ASJC Scopus subject areas

存取文件

其它文件與鏈接

指紋

引用此