穿越具有几个未知重量边缘的图的最快方式

Question

鉴于无向和正向加权图G，G的一些边缘具有未知权重。例如，

其中边缘（B，C）具有未知的重量。

遍历从一个到乙花费你。 我们允许通过从乙遍历到ç或反之亦然来导出未知重量E =重量（B，C）并且收费你ë，其成为公知的重量到底。并从A到C到B费用你e + 7总共。

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

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

任何人都可以弄清楚如何做到这一点？

Answer 1

您可以创建第二个图形G'，它将是相同的 - 但没有“未知边缘”。然后，您可以使用全部到所有最短路径算法，并使用算法中的数据填充空白。

Floyd Warshall algorithm为所有的最短路径提供了一个O(n3)。

---

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

Answer 2

不能提供一个完整的解决方案，但其中未知边缘的节点，它看起来相关旅行商问题被访问。

但我认为你找不到先验的最佳解决方案。考虑下面这个例子

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