Improved algorithm for finding next-to-shortest paths |
| |
| Authors: | Shisheng Li Guangzhong Sun Guoliang Chen |
| |
| Affiliation: | National High Performance Computing Center at Hefei, Department of Computer Science, University of Science and Technology of China, Anhui, Hefei 230027, PR China |
| |
| Abstract: | We study the problem of finding the next-to-shortest paths in a weighted undirected graph. A next-to-shortest (u,v)-path is a shortest (u,v)-path amongst (u,v)-paths with length strictly greater than the length of the shortest (u,v)-path. The first polynomial algorithm for this problem was presented in [I. Krasikov, S.D. Noble, Finding next-to-shortest paths in a graph, Inform. Process. Lett. 92 (2004) 117-119]. We improve the upper bound from O(n3m) to O(n3). |
| |
| Keywords: | Graph algorithms Computational complexity Shortest paths |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
