algorithm - 遍历具有多个未知权重边的图的最快方法

Question

给定一个无向正加权图G ， G的一些边具有未知权重。例如，

在此处输入图像描述

其中边缘（B，C）的权重未知。

从A穿越到B花费你7。我们可以通过从B遍历到C来推导出未知的权重e = weight(B,C) ，反之亦然，并花费你e，最终成为一个已知的权重。从A走到C通过B总共花费你e+7。

我的问题是，当给定一个起点时，我们能以多快的速度获得所有未知的重量？也就是说，以尽可能小的成本从起点（例如A ）遍历所有未知的权重边。

未知权重的个数为1的情况很简单。您可以先找出从起点到所需边的顶点的最短路径，然后遍历未知权重边。但是，当未知权重边的数量大于 1 时，我不知道如何解决。

谁能弄清楚如何做到这一点？

score 3 · Accepted Answer

无法提供完整的解决方案，但它看起来与旅行商问题有关，其中未知边是要访问的节点。

但是我认为您无法先验地找到最佳解决方案。考虑这个例子

a-b = 1
b-c = ?
b-d = ?
a-d = 10

如果b-c权重较低（例如 1），则从开始的最短路径a是a-b-c-b-d遍历b-c两次。如果b-c权重较高（例如 100），则最短路径变为a-d-b-c，宁愿使用更便宜的连接a-d而不是遍历b-c两次。

score 1 · Accepted Answer

您可以创建第二个图 1 G'，这将是相同的 - 但没有“未知边” ¹。然后，您可以使用 all to all 最短路径算法，并使用算法中的数据来填补空白。

Floyd Warshall 算法提供了一条全对全的最短路径。O(n³)

(1) 形式上：G'=(V,E',w')其中：
E' = { e | e is in E and w(e) != ? }
w'(e) = w(e) if w(e) != ?

2 回答 2