修改 Dijkstra 算法以找到具有最大权重的最短路径

Question

我需要一段代码来找到具有最大权重的节点之间的最短路径。例如，从 A 到 D 的最快路线，但权重最大：

  - B- --E
     /  \ /
    A    D
     \  / \
      C - -F

所以现在最短的是 ABD 或 ACD。应用权重后，代码应从两条路径中选择最长的路径（违反直觉，是吧？）。

我正在尝试修改 Dijkstra 算法的算法，但最终我只是遍历了整个图。有人知道怎么做吗？即使只是一个让我自己编写代码的算法也会有很大帮助。

Answer 1

运行BFS从图上的源码（假设为s）找到从s到目标t的最短路径的长度，设为d。同时标记 d(s,v) - 从 s 到任意节点 v.
创建 G 的子图 G'=(V',E')，使得：v 在 V' 中只有当它与源 (s) 的距离最多为 d - d(s,v) <= d 时。仅当 u 和 v 都在 V'.

e=(u,v)

E'

创建一个新图 G*=(V*,E*)，其中 V'=V*，如果一条边 (u,v) 在 E* 中，如果它在 E' AND [=34 中=].
使用 w*.

G*

w*(u,v) = -w(u,v)

Bellman Ford

从s到t的G中最重的最短路径权重-d(t)，BF找到的路径就是匹配的

算法的时间复杂度为 O(VE)，因为 Bellman-Ford 是瓶颈。

正确性证明

声明1：从s到t的最短路径不包含任何循环。
通过删除循环我们得到一条更短的路径，证明很简单。

声明 2：从 s 到 t 的所有最短路径都在 G' 中
证明：由于从s到t的所有最短路径的长度都是d，我们只消除了距离s的距离长于[=13]的节点=]，我们只删除最短路径不需要的节点。

声明 3：从 s 到 t 的所有最短路径都在 G* 中。
证明：假设我们删除了最短路径中的一些边(u,v)，并让该路径为s->...->x->u->v->y->...->t。请注意，路径 v->y->..->t 的长度为 d-d(s,u)-1（假设 d(s,u) 是最小的）
但是，请注意从 E* 的构造中，d(s,v) <= d(s,u)（否则 (u,v) 不会被删除）。因此，存在距离 s 的路径 s->...->v->y->...->t：d(s,v) + d-d(s,u)-1 <= d(s,u) + d - d(s,u) -1 <= d-1 - 与 d 的最小值矛盾。

声明4：G*中没有循环。
证明：假设在G*中有一个循环：v1->v2->vk->v1。根据 G' 的定义，所有节点都可以从 s 到达。不失一般性，让我们假设 d(s,v1) 对于所有其他 d(s,vi) 是最小的（否则旋转索引以匹配此假设）。但是有一个路径v1->v2->...->vk->v1，并且d(s,v1)=d(s,v1)。这意味着至少对于这条路径中的一条边 (vi,vi+1)，d(vi) >= d(vi+1) - 这与 E* 的构造相矛盾，并且循环在 G*.

中不存在

说法5：算法正确

从Bellman-Ford的正确性来看，由于G*不包含负环（根本没有环），BF会根据w*在[=36中找到权重最小的路径=].根据 w，从 w* 的构造中，这条路径是具有最大权重的路径。
因为G中的所有最短路径也存在于G*中（并且只有它们），所以这条路径也是G中权重最大的最短路径。

QED

Answer 2

如果你调整权重，你可以使用 Dijkstra。

如果你的最佳路径必须是访问最少节点的路径，你可以使用高惩罚p遍历每条边并减去实际权重：

w' = p − w

惩罚必须选择高于最高权重 w_max 以防止 w[= 出现负值39=]'，Dijsktra 对此不起作用。它还必须足够高，以便真正选择最短路径。对于 n 个节点的图，p 的良好估计可能是：

p ≈ n·w_max

(编辑：我原来的回答建议使用倒数权重w' = 1/w而不是实际权重w作为替代方案。这不一定会给你最短的路径，但它的权重很高，同时遍历很少的边缘。这个解决方案不适用于许多情况。但是，它完全独立于不使用倒数的惩罚方法。）

修改 Dijkstra 算法以找到具有最大权重的最短路径

Modifying Dijkstra's Algorithm to find shortest path with largest weighting

algorithm

graph

dijkstra

nodes

weighted-graph