分類：
單源最短路徑算法。

適用于：
稀疏圖（側重于對邊的處理）。

優點：
可以求出存在負邊權情況下的最短路徑。

缺點：
無法解決存在負權回路的情況。

時間復雜度：
O(NE)，N是頂點數，E是邊數。（因為和邊有關，所以不適于稠密圖）

算法思想：
很簡單。一開始認為起點是“標記點”（dis[1] = 0），每一次都枚舉所有的邊，必然會有一些邊，連接著“未標記的點”和“已標記的點”。因此每次都能用所有的“已標記的點”去修改所有的“未標記的點”，每次循環也必然會有至少一個“未標記的點”變為“已標記的點”。算法實現：

初始化：dis[s] = 0; dis[v] = oo(v != s); pre[s] = 0;（偽代碼） for(int i = 1; i <= n - 1; i++)for(int j = 1; j <= E; j++) ?//注意要枚舉所有邊，不能枚舉點if(dis[u] + w[j] < dis[v]) ?//u, v分別是這條邊連接的兩個點{dis[v] = dis[u] + w[j]pre[v] = u;}

---------------------?
?

總結

以上是生活随笔為你收集整理的Bellman-Ford算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。