我有一個無向且連通（不完整）的頂點圖，其中u和v可以是任何 2 個不同的頂點。我想構建從頂點u開始，通過v，然后回傳到u而不重復任何邊的最小權重電路。這可以通過執行以下操作來完成嗎？
找到從u到v的最短路徑- 稱之為p1
從圖中洗掉p1 的所有組成邊
找到從v到u的新最短路徑- 稱之為p2
將所有洗掉的邊回傳到圖中，并將p1和p2連接在一起 - 稱之為c1
是C1最小重量電路可以構建，考慮通過雙方的約束ü和v？如果是，我如何證明它，如果不是，為什么不呢？
這對我來說似乎很有意義，因為c1中包含的所有路徑本身也是最短路徑，但是我無法完全擺脫我可能會遺漏某些東西的感覺。
編輯：我已將“完全連接圖”更改為“連接圖”。“完全”暗示圖形是完整的，這不是我的意思。
uj5u.com熱心網友回復：
下面是一個反例：
在完整圖的情況下，假設圖中未顯示的所有邊都具有較大的權重（例如 1000）。
該p1會找到最短路徑1 - 1 - 1和排除，禁止實際的答案3 - 1 1 - 3。
我認為您的任務是Vehicle Routing Problem 的一個變體，它是Traveling Salesman Problem的泛化，并且是 NP-hard 問題。
意思是，要解決您的問題，您必須考慮每個此類路徑之間的所有路徑u，v并為每個此類路徑找到最短路徑，避免使用相同的邊。
uj5u.com熱心網友回復：
如果我理解正確的話，這相當于找到從u到v 的兩條邊不相交的路徑，同時最小化它們的總重量。這是流為 2的最小成本流的特例，因此可以在多項式時間內求解，并且可能不是 NP-hard。Suurballe 的演算法針對有向圖解決了它，并且應該可以將其應用于無向圖（似乎這個 Wikipedia 頁面正在嘗試這樣做）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/350528.html
上一篇：創建基本的簡單樹