算法实验--主函数只有五行的Floyed的算法以及最短路径输出 _最短路

历览千载书，时时见遗烈。这篇文章主要讲述算法实验--主函数只有五行的Floyed的算法以及最短路径输出相关的知识，希望能为你提供帮助。
Floyed算法原理：Floyed-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。

点 i 到点 j 的距离：distance(i,j) 点i 到点 k 的距离加上点 k 到点 j 的距离：distance(i,k) + distance(k,j) 如果distance(i,j) < distance(i,k) + distance(k,j)，那么就更新点 i 到点 j 的距离为distance(i,k) + distance(k,j)，同时记录下点k,因为k是点i到点j的最短路径的中的转折点

五行主函数：

public static void floyed(int[][] map)
for(int k = 0; k< length; k++)
for(int i = 0; i< length; i++)
for(int j = 0; j< length; j++)
if(map[i][j]> map[i][k]+map[k][j])
map[i][j] = map[i][k]+map[k][j];

【算法实验--主函数只有五行的Floyed的算法以及最短路径输出】没错时间复杂度为O(n^3)~~;
实际用例

import java.util.ArrayList;

public class Floyed

public static void start(int[][] map,ArrayList[][] path)
int length = map.length;
for(int k = 0; k< length; k++)
for(int i = 0; i< length; i++)
for(int j = 0; j< length; j++)
if(map[i][j]> map[i][k]+map[k][j])
map[i][j] = map[i][k]+map[k][j];
path[i][j].add(k);

public static void main(String[] args)
int[][] map = new int[5][5];
for(int i = 0; i< map.length; i++)
for(int j = 0; j< map[i].length; j++)
map[i][j] = (i==j)? 0 : 1000;

map[0][1] = 3;
map[1][2] = 8;
map[0][4] = -4;
map[1][3] = 1;
map[1][4] = 7;
map[2][1] = 4;
map[3][0] = 2;
map[3][2] = -5;
map[4][3] = 6;
ArrayList< Integer> [][] path = new ArrayList[5][5];
for(int i = 0; i< path.length; i++)
for (int j = 0; j< path[i].length; j++)
path[i][j] = new ArrayList< > ();

Floyed.start(map,path);
for(int i = 0; i< path.length; i++)
for (int j = 0; j < path[i].length; j++)
System.out.print(i + "到" + j+ "路径："+i+"-> ");
for (int z : path[i][j])
System.out.print(z + "-> ");

System.out.println(j+" 距离为"+map[i][j]);

System.out.println();

结果
0到0路径：0-> 0 距离为0
0到1路径：0-> 4-> 1 距离为1
0到2路径：0-> 1-> 3-> 4-> 2 距离为-3
0到3路径：0-> 1-> 4-> 3 距离为2
0到4路径：0-> 4 距离为-4
1到0路径：1-> 3-> 0 距离为3
1到1路径：1-> 1 距离为0
1到2路径：1-> 3-> 2 距离为-4
1到3路径：1-> 3 距离为1
1到4路径：1-> 3-> 4 距离为-1
2到0路径：2-> 3-> 0 距离为7
2到1路径：2-> 1 距离为4
2到2路径：2-> 2 距离为0
2到3路径：2-> 1-> 3 距离为5
2到4路径：2-> 0-> 1-> 3-> 4 距离为3
3到0路径：3-> 0 距离为2
3到1路径：3-> 0-> 2-> 1 距离为-1
3到2路径：3-> 2 距离为-5
3到3路径：3-> 3 距离为0
3到4路径：3-> 0-> 4 距离为-2
4到0路径：4-> 3-> 0 距离为8
4到1路径：4-> 3-> 1 距离为5
4到2路径：4-> 3-> 2 距离为1
4到3路径：4-> 3 距离为6
4到4路径：4-> 4 距离为0
你可能还敢兴趣的图论算法(均附Java实现代码)：