本福特演算法-九游会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).