AF-heap

From Wikipedia, the free encyclopedia

In computer science, the AF-heap was a proposal by M. L. Fredman and D. E. Willard ^[1] for implementing Dijkstra's algorithm.

Using an AF-heap, a graph having m edges can be inserted into an empty graph of n vertices. The algorithm works with an efficiency of O(m + n log n).

[edit] References

1. ^ M. L. Fredman and D. E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Journal of Computer and System Sciences 48, 533-551 (1994)