算法：通过弗洛伊德(Floyd)算法，求出图中任意两个顶点的最短路径

2023-10-28 00:50
文章标签 算法 路径 两个 任意 顶点 floyd 图中 求出 弗洛伊德

本文主要是介绍算法：通过弗洛伊德(Floyd)算法，求出图中任意两个顶点的最短路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

之前我给大家分享过用迪杰斯特拉(Dijkstra)算法求图的最短路径(点我去看看)，今天我再给大家分享一个也是求图的最短路径的弗洛伊德(Floyd)算法

这两个算法都是求图的最短路径，有什么区别呢？
1、Dijkstra算法是求图中一个点到其他所有点的最短路径，Floyd算法是求图中任意两个顶点之间的最短路径
2、Dijkstra算法是通过贪婪算法来实现的，Floyd算法是通过动态规划算法实现的
3、Dijkstra算法的图，所有边的权重不能为负值，Floyd算法的图在不存在负值圈的前提下可以存在负的权重
4、Dijkstra算法在稀疏图上求最短路径更有效率，Floyd算法在稠密图上求最短路径更有效率
5、Dijkstra算法的代码实现比较复杂，Floyd算法的代码实现比较简单

下面是一个图，有A到G七个顶点，顶点间连通用直线连接，直线上的数字代表两点间的权重，可以理解为路程、运输成本等概念，最短路径也就是权重和最小的路径：
在这里插入图片描述
下面的这个矩阵叫邻接矩阵，中间的数字是两个顶点的权重，也就是左边顶点到上面顶点的权重，就是左边顶点和上面顶点交叉的那个数字值。对角线全部为0，也就是顶点自己到自己的权重是0，INF代表无穷大，代表这两点之间不连通。这个邻接矩阵在接下来的代码中是以二维数组来实现的，INF则用Integer.MAX_VALUE来表示，也就是int的最大值：
在这里插入图片描述
下面是Floyd算法的Java代码实现，具体的算法精髓都在代码和其间的详细注释中。读者可以复制代码到IDE中运行，用DEBUG模式来研究算法的具体实现过程，最后控制台会输出示例图中任意两个顶点的最短路径信息：

/*** @author LiYang* @ClassName FloydAlgorithm* @Description Floyd(弗洛伊德)算法求最短路径* @date 2019/10/25 10:46*/
public class FloydAlgorithm {/*** 用Floyd(弗洛伊德)算法求出所有顶点对的最短路径* @param source 图的邻接矩阵* @param distance Floyd(弗洛伊德)算法的距离表* @param path Floyd(弗洛伊德)算法的路径表*/public static void floydAlgorithm(int[][] source, int [][] distance, int[][] path){//矩阵的边长int length = source.length;//初始化距离表和路径表for (int i = 0; i < length; i++) {for (int j = 0; j < length; j++) {//复制矩阵图到距离表distance[i][j] = source[i][j];//初始化路径表path[i][j] = j;}}//重要：运行Floyd(弗洛伊德)算法求所有顶点对的最短路径for (int k = 0; k < length; k++) {for (int i = 0; i < length; i++) {for (int j = 0; j < length; j++) {//如果当前中间顶点的距离小于之前的距离//且中间顶点的两边距离不为无穷大(int最大值)if (distance[i][k] != Integer.MAX_VALUE && distance[k][j] != Integer.MAX_VALUE && distance[i][j] > distance[i][k] + distance[k][j]){//更新距离表distance[i][j] = distance[i][k] + distance[k][j];//更新路径表path[i][j] = path[i][k];}}}}}/*** 将Floyd(弗洛伊德)算法的距离表和路径表，解析为任意两点间的最短路径距离和路径图* @param distance Floyd(弗洛伊德)算法的距离表* @param path Floyd(弗洛伊德)算法的路径表* @param vertexName 顶点名字(以路径表中数字为下标取)*/public static void parseShortestPath(int[][] distance, int[][] path, String[] vertexName){for (int i = 0; i < path.length; i++) {for (int j = 0; j < path.length; j++) {//出发点和目的点不一样，才打印信息//自己到自己，没有意义if (i != j){//下一站的顶点int next = path[i][j];//记录路径，并加入出发点StringBuffer route = new StringBuffer(vertexName[i]);//重要：只要未到达目的点while (next != j){//加入当前顶点route.append(" -> ").append(vertexName[next]);//更新下一站顶点//重要：每次都是找path表的第j列，要么找到下一个顶点，要么找到目的顶点next = path[next][j];}//最后加入目的节点route.append(" -> ").append(vertexName[j]);//输出两个顶点的最短距离，以及最短路径System.out.println(String.format("%s到%s的最短距离为%d，最短路径：%s", vertexName[i], vertexName[j], distance[i][j], route.toString()));}}}}/*** 获取示例图的邻接矩阵* @return*/public static int[][] initGraphMatrix(){//无穷大距离final int INF = Integer.MAX_VALUE;//生成示例图的邻接矩阵int[][] matrix = new int[][]{{0, 12, INF, INF, INF, 16, 14},{12, 0, 10, INF, INF, 7, INF},{INF, 10, 0, 3, 5, 6, INF},{INF, INF, 3, 0, 4, INF, INF},{INF, INF, 5, 4, 0, 2, 8},{16, 7, 6, INF, 2, 0, 9},{14, INF, INF, INF, 8, 9, 0}};//返回图的邻接矩阵return matrix;}/*** 运行Floyd(弗洛伊德)算法求出所有顶点对的最短路径* 提示：如果需要运行自己的图，则需要重新定义initGraphMatrix()* 方法里面的邻接矩阵，并重新定义顶点名数组String[] vertexName* @param args*/public static void main(String[] args) {//生成示例图中的邻接矩阵(自定义邻接矩阵，改下面的方法的返回值)int[][] matrix = initGraphMatrix();//Floyd(弗洛伊德)算法的距离表int[][] distance = new int[matrix.length][matrix.length];//Floyd(弗洛伊德)算法的路径表int[][] path = new int[matrix.length][matrix.length];//运行Floyd(弗洛伊德)算法floydAlgorithm(matrix, distance, path);//邻接矩阵的下标对应的顶点名字(自定义邻接矩阵，改下面字符串数组)String[] vertexName = new String[]{"A", "B", "C", "D", "E", "F", "G"};//根据距离表、路径表、名字数组，解析输出任意两点的最短距离和最短路径parseShortestPath(distance, path, vertexName);}}

运行上面代码的main方法，控制台将会输出示例图中的任意两顶点之间的最短路径详细信息：

A到B的最短距离为12，最短路径：A -> B
A到C的最短距离为22，最短路径：A -> B -> C
A到D的最短距离为22，最短路径：A -> F -> E -> D
A到E的最短距离为18，最短路径：A -> F -> E
A到F的最短距离为16，最短路径：A -> F
A到G的最短距离为14，最短路径：A -> G
B到A的最短距离为12，最短路径：B -> A
B到C的最短距离为10，最短路径：B -> C
B到D的最短距离为13，最短路径：B -> C -> D
B到E的最短距离为9，最短路径：B -> F -> E
B到F的最短距离为7，最短路径：B -> F
B到G的最短距离为16，最短路径：B -> F -> G
C到A的最短距离为22，最短路径：C -> B -> A
C到B的最短距离为10，最短路径：C -> B
C到D的最短距离为3，最短路径：C -> D
C到E的最短距离为5，最短路径：C -> E
C到F的最短距离为6，最短路径：C -> F
C到G的最短距离为13，最短路径：C -> E -> G
D到A的最短距离为22，最短路径：D -> E -> F -> A
D到B的最短距离为13，最短路径：D -> C -> B
D到C的最短距离为3，最短路径：D -> C
D到E的最短距离为4，最短路径：D -> E
D到F的最短距离为6，最短路径：D -> E -> F
D到G的最短距离为12，最短路径：D -> E -> G
E到A的最短距离为18，最短路径：E -> F -> A
E到B的最短距离为9，最短路径：E -> F -> B
E到C的最短距离为5，最短路径：E -> C
E到D的最短距离为4，最短路径：E -> D
E到F的最短距离为2，最短路径：E -> F
E到G的最短距离为8，最短路径：E -> G
F到A的最短距离为16，最短路径：F -> A
F到B的最短距离为7，最短路径：F -> B
F到C的最短距离为6，最短路径：F -> C
F到D的最短距离为6，最短路径：F -> E -> D
F到E的最短距离为2，最短路径：F -> E
F到G的最短距离为9，最短路径：F -> G
G到A的最短距离为14，最短路径：G -> A
G到B的最短距离为16，最短路径：G -> F -> B
G到C的最短距离为13，最短路径：G -> E -> C
G到D的最短距离为12，最短路径：G -> E -> D
G到E的最短距离为8，最短路径：G -> E
G到F的最短距离为9，最短路径：G -> F

这篇关于算法：通过弗洛伊德(Floyd)算法，求出图中任意两个顶点的最短路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/289560。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu2544（单源最短路径）

hdu2544（单源最短路径）

模板题： //题意：求1到n的最短路径，模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
uva 10099（floyd变式）

uva 10099（floyd变式）

题意： 有一个导游要带着一群旅客从一个城市到达另一个城市，每个城市之间有最大的旅客流量限制。 问最少几趟能将这些旅客从一个城市搞到另一个城市。 解析： 用floyd找出最小流量中的最大边，然后次数就是   ceil（总人数 / 最大承载量 - 1），-1的意思是导游每次也要在车上。 ps.老司机哭晕在厕所 代码： #include <iostream>#includ
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2