Journal of the ACM · 1973 · 317 citations · 3 references
ComputingComputer ScienceMathematicsAlgorithmsComputer NetworksAlgorithm AnalysisComputational ComplexityGraph AlgorithmsGraph TheoryRouting AlgorithmsShortest Path AlgorithmsDijkstra's AlgorithmDijkstra’s Algorithm AnalysisNegative Weight GraphsShortest Path ProblemsShortest Paths
An assertion that Dijkstra's algorithm for shortest paths (adapted to allow arcs of negative weight) runs in O ( n 3 ) steps is disproved by showing a set of networks which take O ( n 2 n ) steps.
3
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Robert W. Floyd · Communications of the ACM · 1962 · 4K citations · Full text