[usamec]

There is no reason to implement fibonacci heap for Dijkstra. Either you have relatively small data (up to 10 mil. nodes and edges) and normal heap is a way faster or you have bigger data and you should start thinking about things like A* where fibonacci heap is again useless.

You should note, that log n factor is so small (up to 40 on the biggest data you will ever see), that it can be easily dominated by other constant factors in implementation (like cache locality, ...).

[m3koval]

Why would you not use A* from the beginning? It's a trivial extension to Dijkstras and is often orders of magnitude faster when an informative heuristic is available.

Also, both algorithms require identical data structures. After all, Dijkstras is just A* with a zero heuristic.

I do agree about the constant factor, though: it's likely that a binary heap would be faster on most data sets.