Floyd算法求有權圖（非負權）的最短路徑并打印

wangxinarhat 發布于2019-08-16 18:34 / 1436人閱讀

摘要：網上關于這個的證明文章非常的少，如果有大佬有嚴謹的證明過程還望不吝賜教。結合大佬的回答和自己的搜索，找到一篇還不錯的證明和原理分析的文章。

狀態轉移方程：d(i,j) = min(d(i,j),d(i,k)+d(k,j))，其中i思路對于每一個k(i

public class FloydTest {
  private static int[][] matrix;

  private static int[][] path;

  public static void main(String[] args) {

    initMatrixAndPath(
            new int[][]{
                    {0, 1, 8, 5},
                    {1, 0, 7, 6},
                    {8, 7, 0, 2},
                    {5, 6, 2, 0}}
    );


    floyd(matrix, path);
    printShortDistance();
    printShortDistanceDetail();
  }

  private static void initMatrixAndPath(int[][] matrix) {
    FloydTest.matrix = matrix;
    FloydTest.path = new int[matrix.length][matrix.length];

    for (int i = 0; i < FloydTest.matrix.length; i++) {
      for (int j = 0; j < FloydTest.matrix[i].length; j++) {
        path[i][j] = j;
      }
    }
  }

  private static void floyd(int[][] matrix, int[][] path) {
    for (int k = 0; k < matrix.length; k++) {
      for (int i = 0; i < matrix.length; i++)
        for (int j = 0; j < matrix.length; j++) {
          if (matrix[i][j] > matrix[i][k] + matrix[k][j]) {
            matrix[i][j] = matrix[i][k] + matrix[k][j];
            path[i][j] = path[i][k];
          }
        }
    }


  }

  private static String getNodeName(int nodeIndex) {
    return "v" + nodeIndex;
  }

  private static void printShortDistanceDetail() {
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[i].length; j++) {
        int x = j;
        StringBuilder sb = new StringBuilder("最短路徑[v" + i + ",v" + j + "]為:");
        sb.append(getNodeName(x));
        sb.append("<--");
        while (path[i][j] != x) {
          x = path[i][x];
          sb.append(getNodeName(path[i][x]));
          sb.append("<--");
        }
        sb.append(getNodeName(i));

        System.out.println(sb);
      }

    }
  }

  private static void printShortDistance() {
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[i].length; j++) {
        System.out.println("v" + i + "到" + "v" + j + "最短路徑為:" + matrix[i][j]);
      }
    }
  }
}

輸出結果

v0到v0最短路徑為:0
v0到v1最短路徑為:1
v0到v2最短路徑為:7
v0到v3最短路徑為:5
v1到v0最短路徑為:1
v1到v1最短路徑為:0
v1到v2最短路徑為:7
v1到v3最短路徑為:6
v2到v0最短路徑為:7
v2到v1最短路徑為:7
v2到v2最短路徑為:0
v2到v3最短路徑為:2
v3到v0最短路徑為:5
v3到v1最短路徑為:6
v3到v2最短路徑為:2
v3到v3最短路徑為:0
最短路徑[v0,v0]為:v0<--v0
最短路徑[v0,v1]為:v1<--v0
最短路徑[v0,v2]為:v2<--v3<--v0
最短路徑[v0,v3]為:v3<--v0
最短路徑[v1,v0]為:v0<--v1
最短路徑[v1,v1]為:v1<--v1
最短路徑[v1,v2]為:v2<--v1
最短路徑[v1,v3]為:v3<--v1
最短路徑[v2,v0]為:v0<--v3<--v2
最短路徑[v2,v1]為:v1<--v2
最短路徑[v2,v2]為:v2<--v2
最短路徑[v2,v3]為:v3<--v2
最短路徑[v3,v0]為:v0<--v3
最短路徑[v3,v1]為:v1<--v3
最短路徑[v3,v2]為:v2<--v3
最短路徑[v3,v3]為:v3<--v3

其他：看了網上的一些關于floyd算法證明的過程。其實最主要的一點，證明當k為遍歷的最后一個節點時，d(i,k)+d(k,j)取最小值，d(i,k)和d(k,j)也已經為各自的最小值。網上關于這個的證明文章非常的少，如果有大佬有嚴謹的證明過程還望不吝賜教。

ps:結合大佬的回答和自己的搜索，找到一篇還不錯的證明和原理分析的文章。
https://www-m9.ma.tum.de/grap...

云服務器 GPU云服務器最經典的最短路徑算法非負權 floyd算法最短路問題算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/75362.html

【程序員必會十大算法】之弗洛伊德算法

摘要：學習資料迪杰斯特拉計算的是單源最短路徑，而弗洛伊德計算的是多源最短路徑代碼不能設置為，否則兩個相加會溢出導致出現負權創建頂點和邊學習資料迪杰斯特拉計算的是單源最...

JellyBool 2021-09-30 09:47 評論0 收藏0
單源點最短路徑(Bellman-Ford)原理及js實現

摘要：說明算法運行結束后，會得到從源節點到其它所有節點的最短路徑，同時得到每個節點的前驅節點，不能包含負權回路如圖但可以包含圖，這里所說的負權環路是指環路的權值總和為正或為負圖圖松弛操作概念松弛操作針對的操作對象是圖中的邊，對圖中任意一條邊， 1. 說明 Bellman-Ford算法運行結束后，會得到從源節點 s 到其它所有節點的最短路徑，同時得到每個節點的前驅節點，Bellman-Ford...

Michael_Lin 2019-08-21 18:37 評論0 收藏0
最短路徑算法總結

摘要：對于邊權為正的圖，任意兩個結點之間的最短路，任意一條的結點數不會超過，邊數不會超過。我會說只有三個嗎適用于任何圖，不管有向無向，邊權正負，但是最短路必須存在。定義（還記得這些定義嗎？如果對圖的概念和存儲不了解請點擊鏈接）路徑最短路有向圖中的最短路、無向圖中的最短路單源最短路、每對結點之間的最短路性質對于邊權為正的圖，任意兩個結點之間的最短路，不會經過重復的結點。對于邊權為正的圖，任意...

Tecode 2022-06-28 19:00 評論0 收藏0
【程序員必會十大算法】之迪杰斯特拉算法

摘要：推薦資料推薦學習文章代碼不能設置為否則兩個相加會溢出導致出現負權創建頂點和邊創建圖頂點數得到邊的數目調用算法計算最短路徑推薦資料推薦學習文章代碼 public...

番茄西紅柿 2021-09-29 09:35 評論0 收藏2637
王者編程大賽之五 — 最短路徑

摘要：由于是從頂點到的最短路徑，則有。算法流程根據最短路徑的最優子結構性質，提出了以最短路徑長度遞增，逐次生成最短路徑的算法。相關文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之三背包王者編程大賽之四約瑟夫環首發于樊浩柏科學院自如年底就會擁有 50W 間房子，大家知道每間房房子都是需要配置完才能出租給自如客的，整個房租的配置過程是很復雜的，每天都需要大量的物流師傅將家電、家具...

yuanzhanghu 2019-07-01 12:36 評論0 收藏0