Dijkstra 算法修改
Dijkstra's Algorithm modification
设G (V, E)为一个带非负权重函数的加权有向图
W : E -> {0, 1, 2... W } 对于一些非负整数 W 。如何修改 Dijkstra 算法以在 O(V W + E) 时间内计算从给定源顶点 s 开始的最短路径。
标准 Dijkstra 使用优先级队列并且可以处理浮点值。这允许所有权重彼此不同并且意味着没有上限。
但是现在你有了整数权重和上限：给定这些额外的约束，你应该能够构建一个更快的算法。而且，实际上，您可以通过使用桶（每个桶对应一个权重）来存储节点。
完整：
- 创建标记为
0, 1, 2, 3, ..., W(V-1) 的存储桶，其中 W 是最大权重，V 是节点数。桶 k 将包含标有距离 k 的所有节点。每个桶都可以用向量或节点列表表示。
- 桶
0, 1, 2, ..., WV 按顺序检查，直到找到第一个非空桶。此桶中的节点位于边界。
- 这个桶中的每个节点都标有它的真实距离，然后从桶中删除。
- 现在重复步骤 (2-4)（尽管在 2 中开始扫描您刚刚清空的桶），直到所有桶都为空。
您需要 WV 个桶来解决 W=1 但图表是一条线的退化情况。在这种情况下，两个节点的最远距离可以是 W(V-1).
有更完整的解释 here。
我曾经研究过这个话题，你要找的算法是Dial algorithm。还有Dijkstra算法的进一步优化，所以我也附在下面。在最底部，我对这三种算法的性能进行了测试。
拨号算法
伪代码
小权重的高效算法。我们为从 0 到最大权重的每个权重使用桶，而不是优先级队列。复杂度为 O(m+n*C)，其中 n 是顶点数，C 是最大成本，m 是边数。
另一种方法是Radix algorithm。
基数堆
伪代码
现在，我们有 ln(C) 个存储桶。 ith bucket 存储 [2^i, 2^(i+1)] 范围内的边。复杂度变为 O(m+nln(n*C)).
测试
测试 1
测试 2
测试 3
测试 4
设G (V, E)为一个带非负权重函数的加权有向图
W : E -> {0, 1, 2... W } 对于一些非负整数 W 。如何修改 Dijkstra 算法以在 O(V W + E) 时间内计算从给定源顶点 s 开始的最短路径。
标准 Dijkstra 使用优先级队列并且可以处理浮点值。这允许所有权重彼此不同并且意味着没有上限。
但是现在你有了整数权重和上限：给定这些额外的约束，你应该能够构建一个更快的算法。而且，实际上，您可以通过使用桶（每个桶对应一个权重）来存储节点。
完整：
- 创建标记为
0, 1, 2, 3, ..., W(V-1)的存储桶，其中W是最大权重，V是节点数。桶k将包含标有距离k的所有节点。每个桶都可以用向量或节点列表表示。 - 桶
0, 1, 2, ..., WV按顺序检查，直到找到第一个非空桶。此桶中的节点位于边界。 - 这个桶中的每个节点都标有它的真实距离，然后从桶中删除。
- 现在重复步骤 (2-4)（尽管在 2 中开始扫描您刚刚清空的桶），直到所有桶都为空。
您需要 WV 个桶来解决 W=1 但图表是一条线的退化情况。在这种情况下，两个节点的最远距离可以是 W(V-1).
有更完整的解释 here。
我曾经研究过这个话题，你要找的算法是Dial algorithm。还有Dijkstra算法的进一步优化，所以我也附在下面。在最底部，我对这三种算法的性能进行了测试。
拨号算法
伪代码
小权重的高效算法。我们为从 0 到最大权重的每个权重使用桶，而不是优先级队列。复杂度为 O(m+n*C)，其中 n 是顶点数，C 是最大成本，m 是边数。
另一种方法是Radix algorithm。
基数堆
伪代码
现在，我们有 ln(C) 个存储桶。 ith bucket 存储 [2^i, 2^(i+1)] 范围内的边。复杂度变为 O(m+nln(n*C)).