floyd算法詳解

一、floyd算法求任意兩點之間的最短路（實質上是動态規劃）：

      算法原理：i、j 兩點間的最短路徑隻有兩種情況：直接從 i 到 j 或者通過中轉點。

                       設map[i][j][k]表示從 i 到 j ，以 0—— k 号點作為中轉點所能得到的最大值。以 0 作為中轉點就表示 i 直接到j，不通過其他點中轉點；可以從1到k号點鐘選取若幹點作為中轉點，也可以直接不選取任何點作為中轉點。

                       那麼狀态轉移方程如下：

                       map[i][j][k]=min{map[i][j][k],map[i][k][k-1]+map[k][j][k-1]}

                       （看了這個遞推式，或許也明白為什麼floyd三重循環要将 k 放在最外面了吧）

      具體代碼實作：  

<span style="font-size:18px;">初始map[i][j][0]為邊(i,j)的值，若i與j不連通，則初始值按題意确定。
      for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
           for(j=1;j<=n;j++)
              map[i][j][k]=min(map[i][j][k],map[i][k][k-1]+map[k][j][k-1]);</span>
           

      觀察上述代碼，我們發現有幾點可以改進的地方：

      1.對于map數組，我們可以省略 k ，隻用一個二維數組即可，即：map[i][j]

      2.若 i 與 k 相同，後面就沒必要枚舉了，因為 i 如果與 k 相同，那麼就變成不通過中轉點的情況了，而這種情況在初始時就已經處理過了。

      3.若是求最短路，那麼 i 與 j 不相連通時，我們一般都将其權值指派為一個極大值，map[i][k]+map[k][j]就有可能超過資料範圍，繼而變成一個負數，這樣就出錯了，解決辦法就是将上述的加法變成減法。

      最終代碼：

<span style="font-size:18px;">初始map[i][j]的值為邊(i,j)的值，若邊(i,j)不存在，
則按照題意進行指派，比如求最短路時，就指派為一個極大值

for(k=-1;k<=n;k++)
  for(i=1;i<=n;i++)if(i!=k)
    for(j=1;j<=n;j++)if(j!=i && j!=k)
      if(map[i][j]-map[i][k]>map[k][j])
        map[i][j]=map[i][k]+map[k][j];
	</span>
           

二、floyd求任意兩點間的最短路徑并輸出：

       設w[i][j]記錄 i 與 j 是否有邊相連，d[i][j]=k，表示從 i 到 j 的最短路徑，i 的下一個點為 k，則有：   

<span style="font-size:18px;">初始map[i][j]的值為邊(i,j)的值，若邊(i,j)不存在，
則按照題意進行指派，比如求最短路時，就指派為一個極大值
若邊(i,j)存在，則初始p[i][j]的值為j,否則就為-1 

for(k=-1;k<=n;k++)
  for(i=1;i<=n;i++)if(i!=k)
    for(j=1;j<=n;j++)if(j!=i && j!=k)
      if(map[i][j]-map[i][k]>=map[k][j])
        { 
          map[i][j]=map[i][k]+map[k][j];
	  if(w[i][k])d[i][j]=k; 
		} 
 
 </span>
           

      接下來，若要輸出(i,j)的最短路徑，直接輸出 i ，然後輸出 k1=d[i][j]，然後輸出 k2=d[k1][j]，以此内推。      

三、floyd尋找環：

       用w[i][j]記錄邊(i,j)的值，假設存在一個如下的環：

                      map[i][j][k-1]

           i     ————————  j

             ↘                           ↙

                  ↘                 ↙

                       ↘       ↙

                             k

       若map[i][j][k-1]==w[i][j]+w[k][j]，則存在一個環。

       對于求環的算法，要靈活使用，比如求最大環，最小環，環的最大、最小權值等等。

       鑒于此，這裡就不給出代碼了，相關例題可以去我的部落格查找，我的每篇文章後面都是注明了使用算法以及求解問題的，找起來還是比較友善（當然，沒有的話，額。。。。，那就這樣吧）