The Necessary and Sufficient Condition for Dijkstra’s Algorithm Applicability
Abstract
Dijkstra’s algorithm is one of the most popular and fundamental algorithms solving the shortest path problem in directed graphs (digraphs). It is well known that Dijkstra’s algorithm is applicable to digraphs with non-negative weighted arcs. But as simple observations show there are many digraphs and even classes of digraphs with negatively weighted arcs for which the Dijkstra’s algorithm is also applicable. Thus the non-negative weight of the arcs condition is not a necessary condition but only a sufficient one. pagebreak The necessary condition for applicability of Dijkstra’s algorithm was unknown. In this paper, we present and prove a necessary and sufficient condition for the applicability of Dijkstra’s algorithm. The condition is based on the notion of a path's record that we introduce.
References
2. Новиков Ф. А. Дискретная математика. 3-е изд. СПб.: Питер, 2017.
3. Anderson J. A. Discrete Mathematics with Combinatorics (2nd Edition). Prentice Hall, 2003.
4. Levitin A. Introduction to the design & analysis of algorithms (3rd Edition). Addison-Wesley, 2012.
5. Cormen T. H., Leiserson Ch. E., Rivest R. L., Stein C. Introduction to Algorithms (3rd Edition). The MIT Press, 2009.
6. Липский В. Комбинаторика для программистов. M.: Mир, 1988.
7. Романовский И. В. Дискретный анализ. 4-е издание. СПб.: Невский диалект, 2008.
8. Алексеев В. Е., Таланов В. А. Графы. Модели вычислений. Струкутры данных. Нижний Новгород: Изд-во ННГУ, 2005.
This work is licensed under a Creative Commons Attribution 4.0 International License.
