最短路徑，2個權重函數

Question

問題是這樣的： 給出了一個有向圖G =（V，E），兩個頂點s，t和兩個權重函數w1，w2。 G中沒有負的加權循環（w1和w2）。 我需要描述一個算法，找出從s到t的給定最短路徑s中從s到t的最短路徑。

我找到了這個： FInding All Shortest Paths Between Two Vertices 但答案似乎對我來說非常大。

我不知道如何解決這個問題（甚至是一個蹩腳的問題）。 任何幫助，將不勝感激。

Answer 1

這個想法是讓w2重要 - 但不足以影響w1的結果。

設SUM2是w2上所有邊緣的總和：SUM2 = Sum { w2(e) | e in E }在此基礎上，和min{w1} = min { w1(e) | e in E }（根據w1最小值）

，創建新的權重函數：

w(e) = w1(e) + w2(e)/min{w1}*(SUM2+1) 

現在，鑑於根據w1的所有最短路徑 - 很明顯爲什麼根據w2的最短路徑將在它們之間受到青睞。

在另一方面，w2是不是「強」，足以克服w1和支配的重要性，因爲需要注意的是，根據w2所有邊的組合總和是w1

比單個節點現在少使用上述w與任何最短路徑算法來獲得您想要的最短路徑。