A quadratic algorithm for finding next-to-shortest paths in graphs (Q639280)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A quadratic algorithm for finding next-to-shortest paths in graphs |
scientific article; zbMATH DE number 5948542
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A quadratic algorithm for finding next-to-shortest paths in graphs |
scientific article; zbMATH DE number 5948542 |
Statements
A quadratic algorithm for finding next-to-shortest paths in graphs (English)
0 references
20 September 2011
0 references
Given an edge-weighted undirected graph and two prescribed vertices \(u\) and \(v\), a next-to-shortest \((u,v)\)-path is a shortest \((u,v)\)-path amongst all \((u,v)\)-paths having length strictly greater than the length of a shortest \((u,v)\)-path. In the paper there is proposed an \(\mathcal O(n^2)\) algorithm for finding a next-to-shortest \((u,v)\)-path.
0 references
next-to-shortest path
0 references
algorithm
0 references
edge weighted graph
0 references
