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 journalArticlepeer-review

1 Citation (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 languageEnglish
Pages (from-to)205-211
Number of pages7
JournalNetworks
Volume65
Issue number3
DOIs
Publication statusPublished - 2015 May 1
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'The next-to-shortest path problem on directed graphs with positive edge weights'. Together they form a unique fingerprint.

Cite this