成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Floyd算法求有權(quán)圖（非負(fù)權(quán)）的最短路徑并打印

wangxinarhat / 1440人閱讀

摘要：網(wǎng)上關(guān)于這個(gè)的證明文章非常的少，如果有大佬有嚴(yán)謹(jǐn)?shù)淖C明過程還望不吝賜教。結(jié)合大佬的回答和自己的搜索，找到一篇還不錯(cuò)的證明和原理分析的文章。

狀態(tài)轉(zhuǎn)移方程：d(i,j) = min(d(i,j),d(i,k)+d(k,j))，其中i思路對(duì)于每一個(gè)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]);
      }
    }
  }
}

輸出結(jié)果

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

其他：看了網(wǎng)上的一些關(guān)于floyd算法證明的過程。其實(shí)最主要的一點(diǎn)，證明當(dāng)k為遍歷的最后一個(gè)節(jié)點(diǎn)時(shí)，d(i,k)+d(k,j)取最小值，d(i,k)和d(k,j)也已經(jīng)為各自的最小值。網(wǎng)上關(guān)于這個(gè)的證明文章非常的少，如果有大佬有嚴(yán)謹(jǐn)?shù)淖C明過程還望不吝賜教。

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

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/75362.html

相關(guān)文章

  • 【程序員必會(huì)十大算法】之弗洛伊德算法

    摘要：學(xué)習(xí)資料迪杰斯特拉計(jì)算的是單源最短路徑，而弗洛伊德計(jì)算的是多源最短路徑代碼不能設(shè)置為，否則兩個(gè)相加會(huì)溢出導(dǎo)致出現(xiàn)負(fù)權(quán)創(chuàng)建頂點(diǎn)和邊 學(xué)習(xí)資料 迪杰斯特拉計(jì)算的是單源最...

    JellyBool 評(píng)論0 收藏0

  • 單源點(diǎn)最短路徑(Bellman-Ford)原理及js實(shí)現(xiàn)

    摘要：說明算法運(yùn)行結(jié)束后，會(huì)得到從源節(jié)點(diǎn)到其它所有節(jié)點(diǎn)的最短路徑，同時(shí)得到每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，不能包含負(fù)權(quán)回路如圖但可以包含圖，這里所說的負(fù)權(quán)環(huán)路是指環(huán)路的權(quán)值總和為正或?yàn)樨?fù)圖圖松弛操作概念松弛操作針對(duì)的操作對(duì)象是圖中的邊，對(duì)圖中任意一條邊， 1. 說明 Bellman-Ford算法運(yùn)行結(jié)束后，會(huì)得到從源節(jié)點(diǎn) s 到其它所有節(jié)點(diǎn)的最短路徑，同時(shí)得到每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，Bellman-Ford...

    Michael_Lin 評(píng)論0 收藏0

  • 最短路徑算法總結(jié)

    摘要：對(duì)于邊權(quán)為正的圖，任意兩個(gè)結(jié)點(diǎn)之間的最短路，任意一條的結(jié)點(diǎn)數(shù)不會(huì)超過，邊數(shù)不會(huì)超過。我會(huì)說只有三個(gè)嗎適用于任何圖，不管有向無向，邊權(quán)正負(fù)，但是最短路必須存在。定義（還記得這些定義嗎？如果對(duì) 圖的概念 和 存儲(chǔ) 不了解請(qǐng)點(diǎn)擊鏈接）路徑最短路有向圖中的最短路、無向圖中的最短路單源最短路、每對(duì)結(jié)點(diǎn)之間的最短路性質(zhì)對(duì)于邊權(quán)為正的圖，任意兩個(gè)結(jié)點(diǎn)之間的最短路，不會(huì)經(jīng)過重復(fù)的結(jié)點(diǎn)。對(duì)于邊權(quán)為正的圖，任意...

    Tecode 評(píng)論0 收藏0

  • 【程序員必會(huì)十大算法】之迪杰斯特拉算法

    摘要：推薦資料推薦學(xué)習(xí)文章代碼不能設(shè)置為否則兩個(gè)相加會(huì)溢出導(dǎo)致出現(xiàn)負(fù)權(quán)創(chuàng)建頂點(diǎn)和邊創(chuàng)建圖頂點(diǎn)數(shù)得到邊的數(shù)目調(diào)用算法計(jì)算最短路徑 推薦資料 推薦學(xué)習(xí)文章 代碼 public...

    番茄西紅柿 評(píng)論0 收藏2637

  • 王者編程大賽之五 — 最短路徑

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

    yuanzhanghu 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<