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

Question

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

其中 edge(B, C) 的权重未知。

从 A 到 B 花费你 7。我们可以通过从 B 遍历到 C 或从 C 遍历来导出未知权重 e = weight(B,C) 并花费你 < strong>e，最终成为已知权重。从 A 到 C 通过 B 总共花费 e+7。

我的问题是，在给定起点的情况下，我们能以多快的速度得到所有未知的权重？也就是说，从一个起点(例如A ) 成本尽可能低。

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

谁能想出如何做到这一点？

Answer 1

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

但我认为你无法先验地找到最优解。考虑这个例子

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 两次。