尋找最短路徑與無視1的可能性（最長）邊緣

Question

我在想，如果我能以這種方式修改Dijkstra'a Alghorithm： 比方說，有兩個頂點之間的兩條路徑具有下列長度：

5, 8, 6, 9 // sum=28 
2, 4, 8, 25 //sum=39 

第一條路徑較短，但在忽略最長邊緣後，我得到以下總和：19和14，所以我選擇第二條路徑。

也許有不同的方式來解決它，而不使用Dijkstra？

Answer 1

我不確定這個想法是否奏效，但首先它在我看來可以。

對於每個訪問的節點，距離D(n)旁邊，它的路徑上最長邊的長度商店，說L(v)。未訪問的鄰居節點的距離是min D(n) + L(n) - max(L(n), weight(v,n))，對於所有鄰居n被訪問。如果n是到v的路徑上的最後一個節點，則下一個訪問節點的L(v)是max(L(n), weight(v,n))。如果有更多的路徑v（更多n's）具有相同的長度，則選擇一個最大的L(v)。