Dijkstra's algorithm factors into two components: (1) time spent
selecting best paths and (2) time spent updating the best
currently known paths.
In a naive implementation, a best path to every unvisited vertex
is kept. Selection of a best path to a vertex v_0 is made by a
linear scan of the paths (O(V) each time). Locking in a path
causes us to possibly update paths to every vertex v_1 that is
touched by an edge from v_0 (constant time per out edge of v_0).
Overall, time complexity is O(|V||V|) selecting paths, and
O(|E|) updating paths. Since |E| is bounded by |V|(|V| - 1), the
time is O(|V| |V|) (insensitive to density).
Using a min-heap to store best known paths, we spend O(log(|V|))
time selecting each path, but an update takes O(log(|V|)). This
means the total time complexity is O(|V|log(|V|) +
|E|log(|V|)).
In the case of dense graphs, this is worse: O(|V| |V| log(|V|)). We're trying to keep the heap organized to allow fast
extract, but there are too many updates and the heap is changing
too much iteration to iteration. OTOH, if the grpah is sparse,
|E| is in O(|V|), so we reduce the time complexity to O(|V|log(|V|)).
A fib heap keeps the same extract time, but updates are O(1)
amortized. Thus the time complexity is O(|V| log(|V|) +
|E|). If the graph is dense, this is O(|V| |V|) (as good as
naive). If the graph is sparse, this is O(|V|log(|V|)) (as good
as bin heap).
This is useful if we do not know whether the graph is sparse or
dense. However, I am not sure what the constants are on Fib
heaps. If you know the density of the graph, I certainly expect
using the appropriate of the first two ways is superior. Another
thought: you could always speculatively execute both algorithms
and see which finishes first :P
Dijkstra's algorithm factors into two components: (1) time spent selecting best paths and (2) time spent updating the best currently known paths.
In a naive implementation, a best path to every unvisited vertex is kept. Selection of a best path to a vertex v_0 is made by a linear scan of the paths (O(V) each time). Locking in a path causes us to possibly update paths to every vertex v_1 that is touched by an edge from v_0 (constant time per out edge of v_0).
Overall, time complexity is O(|V||V|) selecting paths, and O(|E|) updating paths. Since |E| is bounded by |V|(|V| - 1), the time is O(|V| |V|) (insensitive to density).
Using a min-heap to store best known paths, we spend O(log(|V|)) time selecting each path, but an update takes O(log(|V|)). This means the total time complexity is O(|V|log(|V|) + |E|log(|V|)).
In the case of dense graphs, this is worse: O(|V| |V| log(|V|)). We're trying to keep the heap organized to allow fast extract, but there are too many updates and the heap is changing too much iteration to iteration. OTOH, if the grpah is sparse, |E| is in O(|V|), so we reduce the time complexity to O(|V|log(|V|)).
A fib heap keeps the same extract time, but updates are O(1) amortized. Thus the time complexity is O(|V| log(|V|) + |E|). If the graph is dense, this is O(|V| |V|) (as good as naive). If the graph is sparse, this is O(|V|log(|V|)) (as good as bin heap).
This is useful if we do not know whether the graph is sparse or dense. However, I am not sure what the constants are on Fib heaps. If you know the density of the graph, I certainly expect using the appropriate of the first two ways is superior. Another thought: you could always speculatively execute both algorithms and see which finishes first :P
Anyway, I hope that's not too boring of me.
Edit: Grr. Asterisks.