Implementing Dijkstra's shortest path algorithm using a red/black tree?

Question 1

For starters, it's rare to actually see Dijkstra's algorithm implemented with a Fibonacci heap. Although the Fibonacci heap gives great asymptotic performance (O(m + n log n)), in practice it has such high constant factors that other types of heaps are more efficient.

As to your question - yes, you could use a red-black tree as a priority queue to get O(m log n) performance. This works because you can find the minimum element in a red-black tree in O(log n) time and simulate a decrease-key operation on the tree in time O(log n) by doing a deletion followed by an insertion. However, this is probably not as efficient as using a standard binary heap, since the red-black tree has worse locality of reference and more memory overhead. More generally, you always can use a balanced binary search tree whenever you need a priority queue, though usually doing so is overkill.

Hope this helps!

Question 2

I would not say that Dijkstra's algorithm is implemented using a Fibonacci heap. In fact any heap will do although Fiboncci has the best amortized complexity for different operations(keep in mind though this only shows in really huge graphs). Again using red-black tree will achieve the same computational complexity but will have higher constant as working with red-black trees is more complex.

What you need for this algorithm is only to be able to get the minimum element from a given set. That is what a heap is meant for and thus it is best suited for this problem. A red-black tree can do a lot of other stuff and thus is more complex and preforms worse in this particular case.

Question 3

This is an interesting question. Yes, you can use Red-Black tree to implement, here is an example below:

https://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java