Bellman-Ford Algorithm

Bellman-Ford Algorithm

Dijkstra算法雖然好，但是它不能解決帶負權邊，Floyd-Warshall雖然簡單但時間複雜度高，

而Bellman-Ford 就是那個perfect。

核心代碼：

for (int k=1; k<=n-1; k++)
        for (int i=1; i<=m; i++)
            if(dis[v[i]]>dis[u[i]]+w[i])
                dis[v[i]]=dis[u[i]]+w[i];
           

上面的代碼中，外循環一共循環了n-1次（n為頂點的個數），内循環循環了m次（m為邊的個數），即枚舉每一條邊。

dis數組的作用與Dijkstra算法一樣，是用來記錄原點到其餘各個頂點的最短路徑。

u，v,和w三個數組是用來記錄邊的資訊。

例如第i條邊存儲在u[i],v[i],w[i]中,表示從頂點u[i]到頂點v[i]這條邊（u[i]->v[i])權值為w[i]。

if(dis[v[i]]>dis[u[i]]+w[i])
		dis[v[i]]=dis[u[i]]+w[i];
           

上面這兩行代碼的意思是：看能否通過u[i]->v[i]（權值為w[i]）這條邊，

使得1号頂點到v[i]号頂點的距離變短。

即1号頂點到u[[i]号頂點的距離(dis[u[i]])加上u[i]->v[i]這條邊

（權值為w[i])的值是否比原先1号頂點到v[i]号頂點的距離（dis[v[i]]）要小。

這一點其實與Dijkstra的“松弛”操作一樣的。

隻不過現在要把每條邊都松弛一遍。

總結：最短路徑上最多有n-1條邊，是以Bellman-Ford算法最多有n-1個階段，

在每個階段我們都要對所邊進行松弛操作，

是以就會有些已經求得最短路徑，此後這些頂點的最短路的值就會一直不變了。

若在n-1之前所有的頂點都有了最短路的值就可跳出循環了，進而得到優化。

若已經過n-1個階段，頂點的值還有變，則說明帶有負權的回路