johnson算法(基于稀疏圖上的Johnson算法的詳解)

Johnson算法是一種用于解決帶有負權邊的稀疏圖的最短路徑問題的算法。它的主要思想是通過對圖進行一些變換,使得圖中不存在負權環,然后利用Dijkstra算法求解每對頂點之間的最短路徑。

下面是Johnson算法的詳細步驟:

添加一個新的頂點s到圖中,并且從s到圖中的每個頂點v添加一條權重為0的邊。這樣就得到了一個新的圖G’。

使用Bellman-Ford算法計算從頂點s到圖中每個頂點v的最短路徑長度h(v)。如果Bellman-Ford算法檢測到圖中存在負權環,則算法終止,因為這意味著沒有最短路徑存在。

對于原始圖G中的每個邊(u, v),將邊的權重更新為w’(u, v) = w(u, v) + h(u) - h(v)。這個步驟的目的是消除負權邊,因為在原始圖中存在負權邊時,Dijkstra算法無法正確工作。

對于新的圖G’,使用Dijkstra算法計算從每個頂點u到每個頂點v的最短路徑長度d’(u, v)。根據步驟3中的轉換,最短路徑長度d’(u, v)實際上是原始圖G中頂點u到頂點v的最短路徑長度。

對于每對頂點u和v,計算原始圖G中頂點u到頂點v的最短路徑長度d(u, v) = d’(u, v) - h(u) + h(v)。

最后,根據步驟5得到的結果,可以得到原始圖G中每對頂點之間的最短路徑長度。

Johnson算法的時間復雜度為O(V^2 log V + VE),其中V是頂點的數量,E是邊的數量。雖然該算法在稀疏圖上的時間復雜度相對較高,但它可以處理含有負權邊的圖,并且相對于其他算法來說,它具有更好的性能。