弗洛里德算法

简介

        英文名Floyd

        作用：寻找图中任意两点之间的最短路径

        数据结构：邻接矩阵（二维数组）

思想

                如果说从start到end之间转个弯能使得路径变短,那么就记录更短的路径，

        对所有弯都试一下没到最后取最短的，就是start到end的最短路径

        即distance[start] [end] = distance[start] [turnVertex] +distance[turnVertex] [end]

        条件：distance[start] [turnVertex] +distance[turnVertex] [end] < distance[start] [end]

如图：

模型图

Java代码实现

public class Main {private static Scanner scanner=new Scanner(System.in);private static final Integer INF=65535;public static void main(String[] args) {//1.获取图//获取顶点数量System.out.println("请输入顶点的数量:");int vertex_count= scanner.nextInt();//初始化邻接矩阵int[][]dist=new int[vertex_count][vertex_count];int[][]turn=new int[vertex_count][vertex_count];for(int start=0;start<vertex_count;start++){for(int end=0;end<vertex_count;end++){if(start==end){dist[start][end]=0;}else {dist[start][end] = INF;}turn[start][end]=end;}}//填充矩阵，获取任意两点之间的直接距离System.out.println("请输入边的数量:");int edge_count= scanner.nextInt();System.out.println("请依次输入这些边,如start end dist:");for(int i=0;i<edge_count;i++){int start= scanner.nextInt();int end= scanner.nextInt();int distance= scanner.nextInt();dist[start][end]=distance;}//核心：2.寻找任意两点之间的最短路径for(int turnVertex=0;turnVertex<vertex_count;turnVertex++)  //第一个for控制转折点{for(int start=0;start<vertex_count;start++)     //第二个for控制起点{for(int end=0;end<vertex_count;end++)       //第三个for控制终点{//如果转折之后距离能变得更短，那么就记录更短的路径if(dist[start][turnVertex]+dist[turnVertex][end]<dist[start][end]){//记录更短路径dist[start][end]=dist[start][turnVertex]+dist[turnVertex][end];//记录中间转折点turn[start][end]=turnVertex;}}}}}
}