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.