給定一個具有普通邊和特定邊的無向圖，我們的目標是找到兩個頂點（開始頂點到結束頂點）之間的最短路徑權重之和，并且只走過特定邊等于或少于一次。也就是說，特定的邊有多條，最多只能使用其中的一條。
這是我在 Data-Structure 作業中遇到的一個問題，我堅持在 Graph 中存盤邊權重的第一步。因為Graph中有兩種邊，我不知道如何解決這個問題。
我知道我可以通過使用Dijkstra's Algorithm獲得最短路徑，但是在此程序中，我如何修改演算法以滿足限制的要求？
非常感謝回答我的問題！
uj5u.com熱心網友回復：
解決方法是復制圖形如下：
復制頂點，這樣對于每個原始頂點 A，您都有一個 A 和一個 A'。
如果在原圖中 A 和 B 之間有一條正常邊，那么在新圖中，在 A 和 B 之間以及 A' 和 B' 之間放置一條邊
如果在原始圖中 A 和 B 之間有一條特定的邊，那么在新圖中放置一條從 A 到 B'（不是逆！）和從 B 到 A'（再次：不是逆！ ）。這些邊緣應該是定向的。
如果現在的任務是找到 S 和 D 之間的最短路徑，那么在新圖中解決找到 S 和 D或S 和 D'之間最短路徑的問題，以最短者為準。您可以為此使用 Dijkstra 演算法的標準實作，從 S 開始，并在您找到 D 或 D' 時結束。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/374281.html