Java Floyd算法求有权图（非负权）的最短路径并打印
状态转移方程：d(i,j)=min(d(i,j),d(i,k)+d(k,j))，其中i
思路对于每一个k(i 输出结果 v0到v0最短路径为:0 其他：看了网上的一些关于floyd算法证明的过程。其实最主要的一点，证明求d(i,k)+d(k,j)时，d(i,k)和d(k,j)已经为各自的最小值。网上关于这个的证明文章非常的少，如果有大佬有严谨的证明过程还望不吝赐教。 以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。 声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
publicclassFloydTest{
privatestaticint[][]matrix;
privatestaticint[][]path;
publicstaticvoidmain(String[]args){
initMatrixAndPath(
newint[][]{
{0,1,8,5},
{1,0,7,6},
{8,7,0,2},
{5,6,2,0}}
);
floyd(matrix,path);
printShortDistance();
printShortDistanceDetail();
}
privatestaticvoidinitMatrixAndPath(int[][]matrix){
FloydTest.matrix=matrix;
FloydTest.path=newint[matrix.length][matrix.length];
for(inti=0;i
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