沈阳网站建设公司电话,滁州网站建设推广,免费引流推广怎么做,微信小程序一键生成免费1. 简介 Floyd算法#xff0c;全名为Floyd-Warshall算法#xff0c;亦称弗洛伊德算法或佛洛依德算法#xff0c;是一种用于寻找给定加权图中所有顶点对之间的最短路径的算法。这种算法以1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德的名字命名。 2. 核心思…1. 简介 Floyd算法全名为Floyd-Warshall算法亦称弗洛伊德算法或佛洛依德算法是一种用于寻找给定加权图中所有顶点对之间的最短路径的算法。这种算法以1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德的名字命名。 2. 核心思想 通过考虑图中所有可能的中转点逐步更新两点间的最短路径长度和路径信息直至找到最终的最短路径。有的人也称之为插点法。 3. 图解
3.1 初始化 初始化设置图的邻接矩阵dict其中dict[i][j]表示顶点i到顶点j的直接路径权重如果两顶点不直接相连则设为无穷大INF。 3.2 更新最短路径 更新最短路径把每个节点当作是中转节点更新矩阵中的距离。 通过中间顶点 k 从顶点 i 到顶点 j 的距离 小于 直接从顶点 i 到顶点 j 的距离更新 dist[i][j] dist[i][k] dist[k][j]。 把0作为中转节点此时表中黄色部分是不需要改的都是从0出发或是直接到0的距离, 当更新 dict[1][2]也就是1 - 2 时需判断 1 - 0 和 0 - 2 的和是否比直达的1 - 2更小。 若路径中有INF就无需更新比如此时1 - 0 就是INF表示1 - 2 以 0 作为中转点时不可能比 1 - 2 直达的更小所以此时不需要更新。 更新完 0作为中转节点时 数组为 更新完 1作为中转节点时 数组为 更新完 2作为中转节点时 数组为 更新完 3作为中转节点时 数组为 3.3 结果 最终结果的数组中就是点到点的最短路径。 4. 代码实现 定义了一个4x4的图其中INF表示两个顶点之间没有直接相连的边。然后调用floyd方法计算所有顶点对之间的最短路径并输出结果。
public class Floyd {private static final int INF Integer.MAX_VALUE; public static void floyd(int[][] graph) {int n graph.length; // 获取图的顶点数int[][] dist new int[n][n]; // 初始化矩阵for (int i 0; i n; i) {for (int j 0; j n; j) {dist[i][j] graph[i][j]; }}// 使用Floyd算法计算所有顶点之间的最短路径for (int k 0; k n; k) {for (int i 0; i n; i) {for (int j 0; j n; j) {if (dist[i][k] ! INF dist[k][j] ! INF dist[i][k] dist[k][j] dist[i][j]) { // 更新i到j的最短路径dist[i][j] dist[i][k] dist[k][j];}}}}// 输出所有顶点之间的最短路径for (int i 0; i n; i) {for (int j 0; j n; j) {System.out.print(dist[i][j] );}System.out.println();}}public static void main(String[] args) {int[][] graph {{0, 5 , 3 , 10 },{INF, 0 , 3 , INF},{5 , INF, 0 , 1 },{INF, INF, 4 , 0 }};floyd(graph); }
}5. floyd算法和Dijkstra算法的区别 Floyd算法和Dijkstra算法都是计算图中顶点之间最短路径的著名算法但它们的应用场景、原理和性能存在显著差异。具体分析如下 应用场景 Dijkstra算法适用于单源最短路径问题即从单个源点到其他所有点的最短路径。它不能处理具有负权边的图。Floyd算法用于求解任意顶点对多源最短路径问题的最短路径可以处理负权边但不能处理包含负权回路的图。 算法原理 Dijkstra算法基于贪心策略每次从未确定的顶点中选择一个距离源点最近的顶点然后更新其邻接顶点的距离。该算法需要使用优先队列来选择下一个顶点并且初始时除源点外的所有顶点的距离都设置为无穷大。Floyd算法通过动态规划的方式利用三层嵌套循环来计算所有顶点对之间的最短路径。算法的基本操作是比较(u,k) (k,v)与(u,v)的长度并据此更新(u,v)的长度。 时间复杂度 Dijkstra算法使用优先队列优化后的时间复杂度是O((VE) log V)其中V是顶点数E是边数。如果使用邻接矩阵实现且没有优化复杂度会是O(V^2)。Floyd算法时间复杂度为O(V^3)因为算法需要三层循环遍历所有顶点对和可能的中间顶点。 额外功能 Dijkstra算法可以输出从源点到各顶点的最短路径。Floyd算法可以输出任意两个顶点间的最短路径及其长度。 总之Dijkstra算法适合解决单源最短路径问题尤其是在没有负权边的情况下而Floyd算法适合解决所有顶点对之间的最短路径问题尽管它可以处理负权边的情况却不能容忍负权回路的存在。 6. 总结 总的来说Floyd算法是一种计算图中所有顶点对之间最短路径的动态规划算法它能够处理包含负权边的图但不允许存在负权回路。适用于小型到中等规模稠密图的算法尤其是在需要全局最短路径信息时。对于大型稀疏图或者单源最短路径问题其他算法如Dijkstra算法可能更加合适。
