資訊專欄INFORMATION COLUMN
摘要：網(wǎng)上關(guān)于這個的證明文章非常的少，如果有大佬有嚴謹?shù)淖C明過程還望不吝賜教。結(jié)合大佬的回答和自己的搜索，找到一篇還不錯的證明和原理分析的文章。
狀態(tài)轉(zhuǎn)移方程：d(i,j) = min(d(i,j),d(i,k)+d(k,j))，其中i 輸出結(jié)果 其他：看了網(wǎng)上的一些關(guān)于floyd算法證明的過程。其實最主要的一點，證明當k為遍歷的最后一個節(jié)點時，d(i,k)+d(k,j)取最小值，d(i,k)和d(k,j)也已經(jīng)為各自的最小值。網(wǎng)上關(guān)于這個的證明文章非常的少，如果有大佬有嚴謹?shù)淖C明過程還望不吝賜教。 ps:結(jié)合大佬的回答和自己的搜索，找到一篇還不錯的證明和原理分析的文章。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
https://www-m9.ma.tum.de/grap...
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/75362.html
摘要：學習資料迪杰斯特拉計算的是單源最短路徑，而弗洛伊德計算的是多源最短路徑代碼不能設(shè)置為，否則兩個相加會溢出導致出現(xiàn)負權(quán)創(chuàng)建頂點和邊 學習資料 迪杰斯特拉計算的是單源最...
摘要：說明算法運行結(jié)束后，會得到從源節(jié)點到其它所有節(jié)點的最短路徑，同時得到每個節(jié)點的前驅(qū)節(jié)點，不能包含負權(quán)回路如圖但可以包含圖，這里所說的負權(quán)環(huán)路是指環(huán)路的權(quán)值總和為正或為負圖圖松弛操作概念松弛操作針對的操作對象是圖中的邊，對圖中任意一條邊， 1. 說明 Bellman-Ford算法運行結(jié)束后，會得到從源節(jié)點 s 到其它所有節(jié)點的最短路徑，同時得到每個節(jié)點的前驅(qū)節(jié)點，Bellman-Ford...
摘要：對于邊權(quán)為正的圖，任意兩個結(jié)點之間的最短路，任意一條的結(jié)點數(shù)不會超過，邊數(shù)不會超過。我會說只有三個嗎適用于任何圖，不管有向無向，邊權(quán)正負，但是最短路必須存在。定義（還記得這些定義嗎？如果對 圖的概念 和 存儲 不了解請點擊鏈接）路徑最短路有向圖中的最短路、無向圖中的最短路單源最短路、每對結(jié)點之間的最短路性質(zhì)對于邊權(quán)為正的圖，任意兩個結(jié)點之間的最短路，不會經(jīng)過重復的結(jié)點。對于邊權(quán)為正的圖，任意...
摘要：推薦資料推薦學習文章代碼不能設(shè)置為否則兩個相加會溢出導致出現(xiàn)負權(quán)創(chuàng)建頂點和邊創(chuàng)建圖頂點數(shù)得到邊的數(shù)目調(diào)用算法計算最短路徑 推薦資料 推薦學習文章 代碼 public...
摘要：由于是從頂點到的最短路徑，則有。算法流程根據(jù)最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)，提出了以最短路徑長度遞增，逐次生成最短路徑的算法。相關(guān)文章王者編程大賽之一王者編程大賽之二蓄水池王者編程大賽之三背包王者編程大賽之四約瑟夫環(huán) 首發(fā)于 樊浩柏科學院 自如年底就會擁有 50W 間房子，大家知道每間房房子都是需要配置完才能出租給自如客的，整個房租的配置過程是很復雜的，每天都需要大量的物流師傅將家電、家具...
閱讀 1665·2023-04-26 03:04
閱讀 2584·2019-08-30 15:44
閱讀 3797·2019-08-30 14:15
閱讀 3647·2019-08-27 10:56
閱讀 2981·2019-08-26 13:53
閱讀 2675·2019-08-26 13:26
閱讀 3134·2019-08-26 12:11
閱讀 3688·2019-08-23 18:21
