A Note on Dijkstra's Shortest Path Algorithm 论文
1973Journal of the ACM引用 316
Algorithms and Data CompressionFormal Methods in VerificationData Management and Algorithms
摘要
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.