Abstract
An algorithm for finding all shortest paths in an undirected network is considered. The following two criteria are used: the minimum number of arcs in a path and a minimum path length. The algorithm is analyzed for complexity, and it is empirically shown that, with increasing the network density, its computational efficiency becomes higher than that of the Floyd algorithm adequately modified to find the shortest path with the use of a two-step criterion.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
P. Hansen, “Bicriterion path problems,” in: G. Fandel and T. Gal (eds.), Multiple Criteria Decision Making Theory and Application, Springer, Berlin (1979), pp. 109–127.
A. Warburton, “Approximation of Pareto optima in multiple-objective, shortest-path problems,” Oper. Res., 35, No. 1, 70–79 (1987).
M. Ehrgott and X. Gandibleux, Multiple Criteria Optimization — State of the Art Annotated Bibliographic Surveys, Kluwer, Boston, MA (2002).
N. A. Knyazeva, “The use of logical operations for searching for optimal paths in networks,” in: Proc. 2nd All-Union Conf. “Methods and programs for solving optimization problems on graphs and networks,” Part 1, Theory and Algorithms, Novosibirsk (1982), pp. 85–86.
V. V. Dobrolyubov and V. A. Pedyash, “A network algorithm for finding paths with a minimal number of transit nodes and a maximum capacity,” Computing Machinery in Engineering and Communication Systems, No. 4, 129–132 (1979).
E. F. Moore, “The shortest path through a maze,” in: Proc. Intern. Symp. on the Theory of Switching, Part II, Harvard University Press, Cambridge, MA (1959), pp. 285–292.
A. V. Aho, J. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms [Russian translation], Mir, Moscow (1979).
R. W. Floyd, “Algorithm 97: Shortest path,” Comm. ACM, Vol. 5, 345 (1962).
F. W. Dijkstra, “A note on two problems in connection with graphs,” Numerical Mathematics, Vol. 1, 269–271 (1959).
V. A. Vasyanin and A. I. Savenkov, “An algorithm for finding shortest paths in a network with the use of a two-step criterion,” in: Diskretn. i Ergatich. Sist. Upravl, Collected Scientific Papers, Kyiv (1983), pp. 40–49.
R. E. Bellman, “On a routing problem,” Quart. Appl. Math., 16, No. 1, 87–90 (1958).
A. Shimbel, “Applications of matrix algebra to communication nets,” Bulletin of Mathematical Biophysics, 13, 165–178 (1951).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 122–131, September–October, 2014.
Rights and permissions
About this article
Cite this article
Vasyanin, V.A. A Two-Criterion Lexicographic Algorithm for Finding All Shortest Paths in Networks. Cybern Syst Anal 50, 759–767 (2014). https://doi.org/10.1007/s10559-014-9666-9
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-014-9666-9