穿越具有幾個未知重量邊緣的圖的最快方式

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