本福特演算法-九游会j9娱乐平台

『壹』 最短路徑演算法

最短路徑的演算法主要有三種：floyd演算法、dijkstra演算法、bellman-ford(貝爾曼-福特)

一、floyd演算法

基本思想如下：從任意節點a到任意節點b的最短路徑不外乎2種可能，1是直接從a到b，2是從a經過若干個節點x到b。所以，我們假設dis(ab)為節點a到節點b的最短路徑的距離，對於每一個節點x，我們檢查dis(ax) dis(xb) < dis(ab)是否成立，如果成立，證明從a到x再到b的路徑比a直接到b的路徑短，我們便設置dis(ab) = dis(ax) dis(xb)，這樣一來，當我們遍歷完所有節點x，dis(ab)中記錄的便是a到b的最短路徑的距離。

三、bellman-ford(貝爾曼-福特)

演算法的流程如下：

給定圖g(v, e)（其中v、e分別為圖g的頂點集與邊集），源點s，

1.數組distant[i]記錄從源點s到頂點i的路徑長度，初始化數組distant[n]為, distant[s]為0；

2.以下操作循環執行至多n-1次，n為頂點數：
對於每一條邊e(u, v)，如果distant[u] w(u, v) < distant[v]，則另distant[v] = distant[u] w(u, v)。w(u, v)為邊e(u,v)的權值；
若上述操作沒有對distant進行更新，說明最短路徑已經查找完畢，或者部分點不可達，跳出循環。否則執行下次循環；

3.為了檢測圖中是否存在負環路，即權值之和小於0的環路。對於每一條邊e(u, v)，如果存在distant[u] w(u, v) < distant[v]的邊，則圖中存在負環路，即是說該圖無法求出單源最短路徑。否則數組distant[n]中記錄的就是源點s到各頂點的最短路徑長度。

可知，bellman-ford演算法尋找單源最短路徑的時間復雜度為o(v*e).