使用红/黑树实现Dijkstra的最短路径算法？
我知道Dijkstra的算法实际上是使用斐波那契堆实现的。但是，它也可以使用红色的黑树来实现，并且仍然具有O（m log n）的最坏情况运行时间吗？
共有3个答案
这是一个有趣的问题。是的，你可以用红黑树来实现，下面是一个例子:
https://rosettacode.org/wiki/Dijkstras_algorithm#Java
我不会说Dijkstra的算法是使用斐波那契堆实现的。事实上，任何堆都可以，尽管Fiboncci对于不同的操作具有最佳的摊销复杂性（请记住，尽管这只显示在非常大的图形中）。再次使用红黑树将实现相同的计算复杂性，但由于使用红黑树更复杂，因此将具有更高的常数。
这个算法需要的只是能够从给定的集合中得到最小元素。这就是堆的用途，因此它最适合这个问题。红黑树可以做很多其他事情，因此更复杂，在这种特殊情况下表现更差。
首先，很少看到Dijkstra算法是用Fibonacci堆实现的。虽然Fibonacci堆提供了很好的渐近性能(O(m n log n))，但实际上它有很高的常数因子，其他类型的堆更有效。
至于你的问题——是的，你可以使用红黑树作为优先级队列来获得O（m log n）性能。这是有效的，因为你可以在O（log n）时间内找到红黑树中的最小元素，并在O（log n）时间内通过执行删除和插入来模拟树上的减键操作。然而，这可能不如使用标准二进制堆有效，因为红黑树的引用局部性更差，内存开销更大。更一般地说，每当您需要一个优先级队列时，您总是可以使用平衡二叉查找树，尽管通常这样做是多余的。
希望这有帮助！
-
本文向大家介绍java实现Dijkstra最短路径算法，包括了java实现Dijkstra最短路径算法的使用技巧和注意事项，需要的朋友参考一下 任务描述：在一个无向图中，获取起始节点到所有其他节点的最短路径描述 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 Dijkstra一般的表述
-
本文向大家介绍java实现dijkstra最短路径寻路算法，包括了java实现dijkstra最短路径寻路算法的使用技巧和注意事项，需要的朋友参考一下 【引用】迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。 基本思想 通过Dijkstra计算图G中的最短路径时，需要指
-
本文向大家介绍java实现最短路径算法之Dijkstra算法，包括了java实现最短路径算法之Dijkstra算法的使用技巧和注意事项，需要的朋友参考一下 前言 Dijkstra算法是最短路径算法中为人熟知的一种，是单起点全路径算法。该算法被称为是“贪心算法”的成功典范。本文接下来将尝试以最通俗的语言来介绍这个伟大的算法，并赋予java实现代码。 一、知识准备： 1、表示图的数据结构 用于存储图的
-
本文向大家介绍Dijkstra算法最短路径的C++实现与输出路径，包括了Dijkstra算法最短路径的C++实现与输出路径的使用技巧和注意事项，需要的朋友参考一下 某个源点到其余各顶点的最短路径 这个算法最开始心里怕怕的，不知道为什么，花了好长时间弄懂了，也写了一遍，又遇到时还是出错了，今天再次写它，心里没那么怕了，耐心研究，懂了之后会好开心的，哈哈 Dijkstra算法： 图G 如图：若要求从顶
-
本文向大家介绍python实现Dijkstra算法的最短路径问题，包括了python实现Dijkstra算法的最短路径问题的使用技巧和注意事项，需要的朋友参考一下 迪杰斯特拉（Dijkstra）算法主要是针对没有负值的有向图，求解其中的单一起点到其他顶点的最短路径算法。 1 算法原理 迪杰斯特拉（Dijkstra）算法是一个按照路径长度递增的次序产生的最短路径算法。下图为带权值的有向图，作为程序中
-
我已经从Cormen的第三版参考“算法介绍”中找到的伪代码中实现了Dijkstra算法，用于单源最短路径问题。 我的实现是在python上使用链接列表在邻接列表表示中表示图形。这意味着节点列表是一个链接列表，每个节点都有一个链接列表来表示每个节点的边缘。此外，我没有实现或使用任何二进制堆或斐波那契堆作为算法所需的最小优先级队列，因此当过程需要提取与源距离最小的下一个节点时，我在节点链表内搜索O（V