Dijkstra的算法修改

Question

让我们G (V, E)对一个W : E -> {0, 1, 2... W }非负整数使用具有非负权重函数的加权有向图 W。如何修改Dijkstra的算法以从给定的源顶点及时计算出最短路径O(V W + E)。

Answer 1

标准 Dijkstra 使用优先级队列并可以处理浮点值。这允许所有权重彼此不同并且意味着没有上限。

但现在你有了整数权重和上限：考虑到这些额外的约束，你应该能够构建更快的算法。事实上，您可以通过使用桶（每个权重一个）来存储节点。

在全：

1. 创建标记为桶0, 1, 2, 3, ..., W(V-1)，其中W是最大权重，V是节点数。Bucketk将包含所有标有 distance 的节点k。每个桶可以由向量或节点列表表示。
2. 依次检查桶0, 1, 2, ..., WV，直到找到第一个非空桶。该桶中的节点位于边界。
3. 该桶中的每个节点都标有其真实距离，然后从桶中删除。
4. 现在重复步骤 (2-4)（尽管在刚刚清空的存储桶处开始扫描 2），直到所有存储桶都为空。

您需要存储桶来解决图形是一条线的WV退化情况。W=1在这种情况下，两个节点相距最远的距离是W(V-1)。

更完整的解释可以在这里找到。

Answer 2

我曾经对这个主题进行过研究，您正在寻找的算法是Dial algorithm。还有Dijkstra算法还有进一步的优化，所以我也附在下面。在最底部，我对这三种算法进行了性能测试。

拨号算法

伪代码

小权重的高效算法。我们对从 0 到最大权重的每个权重使用存储桶，而不是优先级队列。复杂度是O(m+n*C)其中n是顶点数，C是最大成本，m是边数。

另一种方法是Radix algorithm。

基数堆

伪代码

现在，我们有ln(C)桶了。ith Bucket 存储 range 中的边[2^i, 2^(i+1)]。复杂度变为O(m+nln(n*C)).

测试

测试1

测试2

测试3

测试4