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