A Note on Dijkstra's Shortest Path Algorithm

D. Barton Johnson

Journal of the ACM · 1973 · 317 citations · 3 references

DOIFull text

Open access

Concepts

Abstract

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.

References

3