1

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

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

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

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

4

2 回答 2

2
  1. 从图上的源（顺其自然）运行BFS以找到从到目标s的最短路径的长度，顺其自然。还标记-从到任何节点的距离。stdd(s,v)sv
  2. 创建这样的子图G'=(V',E')：Gis vinV' 仅当它与源 ( s) 的距离最多为d-时d(s,v) <= d。e=(u,v)仅在以下情况E'下才存在：两者u和v都在 中V'。
  3. 创建一个新图G*=(V*,E*)，其中V'=V*和 一条边(u,v)在其中，E*如果它在E'AND中d(s,u) < d(s,v)。
  4. 设置一个新的权重函数w*(u,v) = -w(u,v)，运行Bellman Ford on G*using w*。
  5. Gfrom sto中最重的最短路径是有权t重-d(t)的，BF 找到的路径就是匹配的路径。

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

正确性证明

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

主张 2：所有从sto 到的最短路径t都在G'
证明中：由于从sto 到t的所有最短路径的长度为d，并且我们只删除了距离s大于d的节点，因此我们只删除了最短路径不需要的节点。

s主张 3：从到的所有最短路径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* 中不存在循环。G*v1->v2->vk->v1sd(s,v1)d(s,vi)d(s,v1)=d(s,v1)(vi,vi+1)d(vi) >= d(vi+1)E*

权利要求 5：算法是正确的。

从 Bellman-Ford 的正确性来看，由于G*不包含负循环（根本没有循环），BF 将根据w*in找到具有最小权重的路径G*。这条路径是根据w，从构造上具有最大权重的路径w*。
由于所有最短路径G也存在于G*（并且仅存在于它们）中，因此该路径也是G具有最大权重的最短路径。

量子点

于 2015-06-04T18:01:02.747 回答
-1

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

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

    w ' = p - w

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

    p ≈ n · w最大值

（编辑：我最初的答案建议使用每条边的倒数权重w ' = 1/ w而不是实际权重w作为替代方案。这不一定会给你最短路径，但在遍历少数边时权重很高. 这个解决方案在很多情况下都不起作用。但是，它完全独立于不使用倒数的惩罚方法。）

于 2015-06-04T18:02:01.647 回答