Dijkstra's algorithm with Fibonacci heap (Johnson 1981; Karlsson & Poblete 1983) (Nonnegative Integer Weights Shortest Path (Directed Graphs))
Jump to navigation
Jump to search
Time Complexity
$O(E \log \log L)$
Space Complexity
$O(V+L)$ words
(https://www.sciencedirect.com/science/article/pii/0166218X8390104X?via%3Dihub)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1981
Reference
https://www.sciencedirect.com/science/article/pii/0166218X8390104X?via%3Dihub