On computing sets of shortest paths in a graph

1 June 1974

journal article
Published by Association for Computing Machinery (ACM) in Communications of the ACM

Vol. 17 (6) , 351-353
https://doi.org/10.1145/355616.364037

Abstract

Two algorithms are presented that construct the k shortest paths between every pair of vertices in a directed graph. These algorithms generalize the Floyd algorithm and the Dantzig algorithm for finding the shortest path between every pair of vertices in a directed graph.

Keywords

This publication has 7 references indexed in Scilit:

A Note on an Algebra for the k Best Routes in a Network
IMA Journal of Applied Mathematics, 1973
The Theory of Networks and Management Science. Part I
Management Science, 1970
An Appraisal of Some Shortest-Path Algorithms
Operations Research, 1969
Algorithm 97: Shortest path
Communications of the ACM, 1962
Solutions of the kth best route through a network — A review
Journal of Mathematical Analysis and Applications, 1961
A note on two problems in connexion with graphs
Numerische Mathematik, 1959
A Method for the Solution of the N th Best Path Problem
Journal of the ACM, 1959