floyd ，dijikstra，Bellman-ford算法詳解

幾乎是瞬間，自己已經是大二了，真得時間過得好快，大一掠過，隻有一些美好的回憶留在心頭。
           

不扯淡了，言歸正傳。

圖論，這名字起的太大了，其實就是一些最基本的算法，用于解決圖上的最短距離的算法。
           

第一個是floyd 算法 很簡單直白的算法，是使用鄰接矩陣來求最短路的算法，其實就是通過點來松弛兩點之間的距離。

例如：

for(int i=1;i<=n;i++)
{ 
   for(int j=1;j<=n;j++)
   {
       if(g[i][j]>g[i][1]+g[1][j])
          g[i][j] = g[i][1]+g[1][j];
   }
}
           

上面的代碼就是通過編号為1的這個點來松弛每兩個點，縮短他們之間的距離

是以整個核心代碼就是：

for(int k=1;k<=n;k++)
{
   for(int i=1;i<=n;i++)
   {
      for(int j=1;j<=n;j++)
      {
         if(g[i][j]>g[i][k]+g[k][j])
             g[i][j] = g[i][k]+g[k][j];
      }
   }
 }
           

之後又出現了dijikstra算法（挺難拼的）

這個算法的思路是通過邊來實作松弛，它是有一個一維數組dis[] 來儲存由1到各個點的距離，首先儲存圖中的初始距離

然後再進行處理，在這之中，是從那些估計值中選擇出最小的值作為源點，因為在這算法中認為所有的邊權，都是正值的，是以最小的邊已經無法再通過其餘的邊進行松弛了，是以選其作為源點。（也正由于這思想，這個算法是無法處理帶有負權邊的圖的）

核心代碼：

while(sum<n)
        {
            int temp=maxn;
            for(int i=;i<=n;i++)
            {
                if(book[i]==)
                {
                    if(temp>dis[i])
                    {
                        temp = dis[i];
                        cur = i;
                    }
                }
            }
            book[cur] = ;
            for(int i=;i<=n;i++)
            {
                if(g[cur][i]<maxn)
                {
                    if(dis[cur]+g[cur][i]<dis[i])
                        dis[i] = dis[cur]+g[cur][i];
                }
            }
            sum++;
        }
           

接下來是完美的Bellman-ford算法

算法簡單 又 完美的解決了負權邊的問題

這個對于圖的儲存有了變化，它是開了三個數組

u[ ] v[ ] w[ ]

存儲各個值

核心代碼：

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

這個算法也是通過邊松弛來優化的。當運作完這個循環，在運作一次内循環，所得結果有所變化時，邊說明圖含有負權邊。