Bellman-Ford的「所有配對」或「從一個節點」最短路徑的結果？ /是否有全套的Bellman-Ford版本？

Question

我最近在學習圖算法，在我的大學裏，我們被教過，Bellman-Ford的結果是從所有節點到所有其他節點（全對最短路徑）的距離表。不過，我不明白這是如何的算法實現，試圖通過觀看YouTube視頻和查找維基百科的定義等等，瞭解它...

現在，這裏是問題：
我找不到資源它以一種方式描述了算法，其結果將是所有對最短路徑表，但僅「從一個節點到所有其他節點」。

可以調整Bellman-Ford算法來實現所有配對最短路徑表，還是我的大學講師完全錯了嗎？ （他做了解釋一些算法，提供所有對的最短路徑，他把它叫做貝爾曼 - 福特，但是我覺得這不可能是貝爾曼福特）

編輯：我完全理解Bellman-Ford算法的問題「最短路徑從一個節點到所有其他節點「。
我也理解大部分在我的大學教過的「所有對最短路徑」算法。
我只是很困惑，因爲我在大學的算法也被稱爲「貝爾曼 - 福特」。
如果你會講德語：這裏是他的「貝爾曼 - 福特」的大學講師會談（我認爲這是不實際貝爾曼 - 福特）視頻：
https://www.youtube.com/watch?v=3_zqU5GWo4w&t=715s

Answer 1

我問我們學校的論壇，得到了如下回答：

貝爾曼 - 福特原本是「從一個節點」。然而，當將原始的Bellman-Ford算法應用於Graph的每個節點時，不變量（算法背後的想法）不會改變。原始的Bellman-Ford的複雜性是O（V^3），並且如果從每個節點開始，它將是O（V^4）。然而，有一種技巧可以使用，因爲算法期間的發現類似於輸入矩陣（包含直接路徑長度）與其自身的矩陣乘法。因爲這是一個數學環，所以可以作弊並且簡單地計算矩陣^ 2，矩陣^ 4，矩陣^ 8等等（這是我沒有完全理解的部分），並且可以實現O（V^3 * log V ）。

他也把這個算法叫做Bellman-Ford，因爲算法背後的不變量/想法仍然是一樣的。

German answer in our public university forum

Answer 2

算法的目的是要找到從起點到終點的最短路徑。

要做到這一點，它會找到從所有點到其他點的最短距離，然後選擇通向解決方案的路徑，並將其加到最短。

首先，它從出發點（A）開始。將每個點的成本設置爲無窮大。

現在它看到所有可能的方向從A和A的初始成本設置爲零。

想象它需要前往只有B.一個有可能是連接B到A和它的成本是說一條直路，10

但也有通過C的路徑從A到C它需要花費5，從C到B它只需要花費2.這意味着從A到B有兩條可能的路徑。一條花費10，另一條5 + 2即7。因此它應該將從A到達B的成本更新到7而不是10，因此應該選擇路徑。

你可以想象這種情況，但有更多的點。它應從起點開始搜索，到達遍歷所有可能路徑的終點，並根據需要更新/不更新成本。最後它應該尋找所有路徑並選擇成本最低的路徑。

現在，這裏是問題：一個我無法找到 的方式，其結果必然是所有 對最短路徑表中描述的算法資源，但只有「從一個節點到所有其他 節點」。

要理解這一點，設想我們必須達到A到D.

從一個點移動到另一個的單個成本低於

• A所列B：15

• A至C：10

• B到C：3

• B to D：5

• C到D：

最初將除A之外的所有點設置爲無窮大爲零。

首先，

A-> B：成本= 15（更新B的成本至15）

A-> C：成本= 10（更新C'S成本至10）

B- > C：成本= 18（B的成本加B-> C單獨成本，所以不要更新爲C的成本，因爲已經小於此成本）

C-> B：成本= 13（C的成本加C-> B單獨成本，更新B的成本爲13，因爲這小於15）

B-> D：成本= 18（B的新成本加上B-> D成本，更新D的成本爲小於無窮大）

C-> D：成本= 25（C的成本加C-> D單獨成本，不更新D）

所以算法選擇的路徑是以18的成本導出D到最小成本的路徑！

 B 
/| \ 
A | D 
    \ |/
    C 

A-> C-> B-> d費用：18

現在你可以閱讀this鏈接，更好的理解。事情應該很清楚。

Answer 3

Bellman Ford是從給定起始節點到圖中任何其他節點的最短路徑的算法。

使用Bellman Ford，如果我們從每個節點運行bellman ford算法，然後得到所有其他最短路徑，那麼算法的最壞情況時間複雜度爲O（V * V * E），並且如果我們有完整的圖，這個複雜度將是O（V^4），其中V是圖中頂點（節點）的數量，並且E是圖中邊緣的數量。

有更好的算法找到所有對最短路徑在O（V^3）時間複雜性。這是Floyd Warshall算法。

在這裏，你可以閱讀更多關於它：https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm