本文主要是介绍算法：弗洛里德算法Floyd，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
弗洛里德算法
简介
英文名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;}}}}}
}这篇关于算法：弗洛里德算法Floyd的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
