Bellman-Ford 演算法

給定有向圖 G，我們經常想要找到從給定節點 A 到圖中其餘節點的最短距離。 Dijkstra 演算法是用於找到最短路徑的最著名的演算法，但是僅當給定圖的邊權重是非負的時它才起作用。然而，貝爾曼 - 福特旨在找到來自給定節點（如果存在）的最短路徑，即使一些權重是負的。請注意，如果圖形中存在負迴圈，則可能不存在最短距離（在這種情況下，我們可以繞過迴圈，從而產生無限小的總距離）。 Bellman-Ford 還允許我們確定這種迴圈的存在。

該演算法的總複雜度為 O(V*E)，其中 V - 是頂點數和 E 邊數