DSA 最短路徑

最短路徑問題

最短路徑問題在計算機科學領域非常有名。

解決最短路徑問題意味著在一個圖中找出兩個頂點（或節點）之間可能的最短路線或路徑。

在最短路徑問題中，圖可以表示任何東西，從道路網路到通訊網路，其中頂點可以是交叉路口、城市或路由器，而邊可以是道路、航班路徑或資料鏈路。

上圖中從頂點 D 到頂點 F 的最短路徑是 D->E->C->F，總路徑權重為 2+4+4=10。從 D 到 F 還有其他可能的路徑，但它們具有更高的總權重，因此不能視為最短路徑。

最短路徑問題的解決方案

Dijkstra 演算法和Bellman-Ford 演算法可以找出從一個起始頂點到所有其他頂點的最短路徑。

解決最短路徑問題意味著檢查圖中的邊，直到找到一條路徑，我們可以在該路徑上使用最低的組合權重從一個頂點移動到另一個頂點。

構成路徑的邊的權重之和被稱為路徑成本或路徑權重。

尋找最短路徑的演算法，例如Dijkstra 演算法或Bellman-Ford 演算法，可以找出從一個起始頂點到所有其他頂點的最短路徑。

首先，演算法將起始頂點到所有頂點的距離設定為無限長。隨著演算法的執行，頂點之間的邊會被一遍又一遍地檢查，並且可能會多次找到更短的路徑，直到最終找到最短路徑。

每次檢查一條邊並發現到某個頂點的距離更短並更新時，這被稱為鬆弛，或者鬆弛一條邊。

正負邊權重

一些尋找最短路徑的演算法，例如Dijkstra 演算法，只能在所有邊都為正的圖中找到最短路徑。這種具有正距離的圖也最容易理解，因為我們可以將頂點之間的邊視為位置之間的距離。

如果我們把邊權重解釋為從一個頂點到另一個頂點所損失的金錢，那麼上圖中從頂點 A 到 C 的正邊權重 4 意味著我們必須花費 4 美元才能從 A 到 C。

但是圖也可以有負邊，對於這樣的圖，可以使用Bellman-Ford 演算法來找到最短路徑。

同樣，如果邊權重代表損失的金錢，那麼上圖中從頂點 C 到 A 的負邊權重 -3 可以理解為一條邊，透過這條邊從 C 到 A 所賺取的金錢比損失的金錢還要多。因此，例如，如果從 C 到 A 的燃料成本是 5 美元，並且我們因在 C 收取包裹並將其運送到 A 而獲得 8 美元，那麼損失的金錢就是 -3 美元，這意味著我們總共賺取了 3 美元。

最短路徑問題中的負環

如果圖中存在負環，則無法找到最短路徑。

存在負環意味著存在一條路徑，您可以在其中迴圈，而構成此迴圈的邊的總路徑權重為負。

在下圖中，路徑 A->E->B->C->A 是一個負環，因為總路徑權重為 5+2-4-4=-1。

在具有負環的圖中無法找到最短路徑的原因是，演算法總是可以繼續執行以找到更短的路徑。

舉例來說，如果我們想找出上圖中頂點 D 到所有其他頂點的最短距離。起初，我們發現 D 到 E 的距離是 3，只需沿著邊 D->E 走即可。但是在此之後，如果我們繞著負環 E->B->C->A->E 走一圈，那麼到 E 的距離就變成 2。再繞一圈後，距離變成 1，更短了，依此類推。我們可以隨時在負環中多繞一圈來找到到 E 的更短距離，這意味著永遠找不到最短距離。

幸運的是，可以在Bellman-Ford 演算法中實現對負環的檢測，該演算法適用於帶有負邊的圖。