我需要一段代码来查找权重最大的节点之间的最短路径。例如，从A到D的最快路线，但权重最大:
- B- --E
/ /
A D
/
C - -F
所以现在最短的是ABD或ACD。一旦应用了权重，代码应该从两个路径中选择最长的路径(违反直觉，是吧?)。
我试图修改Dijkstra算法的算法，但最终我只是结束遍历整个图。有人知道怎么做吗?即使只是一个算法，让我可以自己编码，也会非常有帮助。
- 从源(设为
s)在图上运行BFS以找到从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*在E'和d(s,u) < d(s,v)中，(u,v)在E*中。 - 设置新的权函数
w*(u,v) = -w(u,v)，并使用w*在G*上运行Bellman Ford。 -
G中从s到t的最重最短路径权值为-d(t), BF找到的路径为匹配路径。
算法的时间复杂度为O(VE)，因为Bellman-Ford是瓶颈。
<
正确性证明/strong>
声明1:从s到t的最短路径不包含任何循环。
证明很简单，去掉循环，我们得到了更短的路径。
权利要求2:从s到t的所有最短路径都在G'中
证明:由于从s到t的所有最短路径的长度都是d，并且我们只删除了与s的距离大于d的节点，因此我们只删除了不需要最短路径的节点。
权利要求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->...->v->y->...->t，距离s: 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会根据G*中的w*找到权值最小的路径。该路径是w*构造的w中权重最大的路径。
由于G中的所有最短路径也存在于G*中(且只有它们)，因此该路径也是G中权值最大的最短路径。
QED
你可以使用Dijkstra，如果你调整你的权重。
如果你的最优路径必须是访问最少节点的路径，你可以使用高惩罚p来遍历每条边并减去实际权值:
,,w' = p − w
必须选择高于最高权重wmax，以防止w'的负值，而Dijsktra不起作用。它也必须足够高，这样最短的路径才会被选中。对于n个节点的图，p的一个很好的估计可能是:
,, p 约; n 压力; w <子> max
(编辑:我最初的答案建议使用每条边的倒数权值w' = 1/w作为替代，而不是实际权值w。这并不一定会给你最短的路径，但它的权值很高，而遍历的边很少。这种解决方案在许多情况下并不适用。但是，它完全独立于惩罚方法，惩罚方法不使用倒数值。