Dijkstra算法的修改

Question

让 G（V，E） 成为一个带有非负权重函数的加权有向图， W：E -> {0,1,2 ... W}，其中 W 为非负整数。如何修改 Dijkstra 算法以在 O（VW + E） 时间内计算给定源顶点 s 的最短路径。

- Dhruv Singh

---

你的问题似乎并不完全正确。对于“计算最短路径”的某些解释，可以在O（V * log（V）+ E）时间内完成。如果您实际上必须编写最短路径，例如，其他解释需要O（V ^ 2 + E）时间，如果所有边缘具有相同的权重。 - Matt Timmermans

@MattTimmermans：但是这些权重是整数，并且在这里有上限。这些额外的约束条件通过允许使用更便宜的数据结构来降低时间复杂度。 - Richard

@Richard，如果W < log(V)，那应该会更便宜...我想这可能是个好主意。 - Matt Timmermans

@MattTimmermans：是的（至少渐近地 - 从运行时间的角度来看，找到平衡点会很有趣）。 - Richard

Answer 1

标准的Dijkstra算法使用优先队列，可以处理浮点数值。这允许所有权重彼此不同，并且没有上限。

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

具体步骤如下：

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

你需要 WV 桶来处理退化情况，即当 W=1 但图形是一条直线时。在这种情况下，两个节点之间最远的距离是 W(V-1)。

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

- Richard

---

如果当前节点距离为D，则队列中的所有节点距离都在[D，D + W]范围内，因此您可以使用W + 1个桶的循环数组来实现队列，而不是VW个桶。由于当W <log（V）左右时，桶队列比堆更快，因此这可能是一个巨大的优势。 - Matt Timmermans

@MattTimmermans：这是一个很酷的想法，但我不认为它会导致速度上的差异：对于这两个操作，从桶数组中访问和检索仍然是_O(1)_ 时间。 - Richard

Answer 2

我曾经对这个话题进行过研究，你要找的算法是 Dial算法。还有一个对 Dijkstra算法 进一步优化的方法，我也在下面附上了。最后我将我的三种算法性能测试结果放在了最底部。

Dial算法

伪代码

该算法适用于小权重值，我们使用每个权重从0到最大权重的桶，而不是优先队列。时间复杂度为 O(m+n*C) 其中 n 是顶点数，C 是最大代价，m 是边数。

另一种方法是 Radix算法。

Radix堆

伪代码

现在，我们有 ln(C) 个桶。第 i 个桶存储范围在 [2^i, 2^(i+1)] 中的边。时间复杂度变为 O(m+nln(n*C))。

测试

测试1

测试2

测试3

测试4

- xenteros