弗洛伊德(Floyd)算法(C/C++)

2024-08-28 18:12
文章标签 算法 c++ floyd 弗洛伊德

本文主要是介绍弗洛伊德(Floyd)算法(C/C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

弗洛伊德算法(Floyd's algorithm),又称为弗洛伊德-沃尔什算法(Floyd-Warshall algorithm),是一种用于在加权图中找到所有顶点对之间最短路径的算法。这个算法适用于有向图和无向图,并且可以处理负权重边,但不能处理负权重循环。

弗洛伊德算法(Floyd-Warshall Algorithm)是一种用于计算图中所有顶点对之间最短路径的动态规划算法。本文将详细介绍弗洛伊德算法的原理,并提供一个C++实现的示例,以帮助读者理解算法的工作原理和编程技巧。

算法原理

弗洛伊德算法的核心思想是通过逐步寻找并更新所有顶点对之间的最短路径来解决问题。算法使用一个距离矩阵来存储顶点之间的距离,并在每一步中考虑通过一个新的中间顶点来更新这些距离。跟上一篇Dijkstra算法一样的原理,也是通过中转点去更新最短距离。不过Floyd算法处理的是多源的最短路问题


算法步骤

  1. 初始化一个距离矩阵,其中dist[i][j]表示顶点i到顶点j的直接距离。如果ij不直接相连,则dist[i][j]为无穷大。
  2. 对于每个顶点k,作为中间顶点,更新dist[i][j]min(dist[i][j], dist[i][k] + dist[k][j])

Floyd是经典三重for循环,所以它的时间复杂度为o(n^3),n是图中顶点的数量。第一层遍历中转点,第二层遍历起点,第三层遍历终点,对于图中点的数量多的情况,Floyd算法的时间复杂度是很高的。

图解算法:

下面我们将以4个点的图进行讲解,图的连边为有向边和无向边的结合。以邻接矩阵的方式进行存储,如果大家喜欢用邻接表存储,也可以使用邻接表,下面介绍两个矩阵,矩阵A表示(i,j)i->j的最短距离,初始化为inf。矩阵B表示i->j路径由i到j的中转点,也就是路径上除去起点的第一个点,初始化为-1。

初始:

按照图中的点距离给其赋值,A矩阵i->i距离都为0,inf为无法到达。B矩阵初始为-1。

第一步:

我们选取一个点(按照顺序选取)把它作为中转点,看看以它为中转点,所能到达的点中有没有产生更小的距离,如果产生了,则更新A矩阵的距离,更新B矩阵的中转点。我们先选取1号点,那么位于1号点的行跟列的值都是不可能变化的,还有就是自己到自己的点也是不会变化的永远是0,图中黄颜色标记的是此步不会改变的点,其他的可能会变。在更新距离的时候我们可以不看图就能更新矩阵,例如下图中2号点到3号点本来为10,我们可以连一个矩阵,以1号点画的两条蓝线为两条边,红色线为剩余2边,我们既然把1号点当作中转点,路径必然为2-1-3,此时距离就是副对角线的顶点值相加2+6=8<10,那么通过1号点绕路的方式距离更短。类似的还有3->2号点,6+2=8<inf。3->4号点,10+6=16<inf。4->3号点,10+6=16<inf。顺便把B矩阵更新完。

更新完后(红色标记为变化的值): 

 第二步:

此时把2号结点作为中转结点,看一看能够更新哪一个最短路径,还是跟上一步一样直接看图更新就可以。如下图,4->1号点,2+4=6<10。1->4号点,2+4=6<10。3->4号点,8+4=12<16。4->3号点,8+4=12<16。对于一些不能更新的值,例如1->3号点,2+8=10>6,这样的则不能更新。

对于B矩阵,要注意3->4跟4->3的路径是相反的,更新是则不能直接修改为2,对于3->4号点第一个中转点还是1号点。更新完后(红色标记为变化的值): 

第三步:

把3号点作为中转结点,跟前几步一样,继续寻找最短距离。经过更新我们发现3号点作为中转点不能更新任意一个距离,所以A、B矩阵不需要更新。在图中,经过验证我们发现3号点中转距离反而变大,所以不更新。

第四步:

把4号点作为中转点,继续更新最短距离。我们发现跟3号点一样,不能更新任何距离,在A矩阵中除了黄色的点之外,所能连起来的矩形,主对角线顶点值相加都比当前值要大。在图中也可以验证,所以不给予更新。

这样我们就更新完所有点,把所有点都当作中转点更新完一遍,这样就完成了Floyd算法,更新时每次按照顺序把点当作中转点,遍历寻找路径的起点,再遍历寻找终点,算法时间复杂度为o(n^3)。

视频讲解可以看一下B站这位UP主的讲解,点击直达


算法实现:

以下是弗洛伊德算法的C++实现示例:

#include <iostream>
#include <vector>
#include <limits>
using namespace std;// 定义图的顶点数
const int N = 100;
// 定义无穷大的初始距离
const int INF = numeric_limits<int>::max();// 弗洛伊德算法的实现
void floydWarshall(vector<vector<int>>& dist) {int n = dist.size();// 遍历所有顶点作为中间顶点for (int k = 0; k < n; k++) {// 遍历所有顶点作为起点for (int i = 0; i < n; i++) {// 遍历所有顶点作为终点for (int j = 0; j < n; j++) {// 如果通过顶点k可以找到更短的路径,则更新dist[i][j]if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}
}int main() {int n; // 顶点的数量cin >> n;vector<vector<int>> dist(n, vector<int>(n, INF)); // 初始化距离矩阵// 读取邻接矩阵for (int i = 0; i < n; i++) {dist[i][i] = 0; // 自己到自己的距离是0for (int j = i; j < n; j++) {int w;cin >> w;dist[i][j] = w;dist[j][i] = w; // 如果是无向图,需要设置对称的权重}}// 执行弗洛伊德算法floydWarshall(dist);// 打印所有顶点对之间的最短路径for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][j] == INF) {cout << "INF" << " ";} else {cout << dist[i][j] << " ";}}cout << endl;}return 0;
}

Floyd与Dijkstra算法比较 

迪杰斯特拉算法(Dijkstra's algorithm)和弗洛伊德算法(Floyd-Warshall algorithm)都是图论中用于计算图中最短路径的著名算法。它们在某些方面有相似之处,但在设计和应用上存在显著差异,下面我们将对这两种算法的相同跟不同进行解释。

相同点:
  1. 目的两者都旨在解决最短路径问题。
  2. 适用性:它们都可以用于加权图中的最短路径计算,无论是正权还是负权(只有弗洛伊德算法)。
不同点:
  1. 问题范围:
    • 迪杰斯特拉算法:主要用于单元路径的最短路问题,即从单一源点到所有其他顶点的最短路径。
    • 弗洛伊德算法:解决的是所有顶点对之间的最短路径问题,即计算图中每一对顶点之间的最短路径。
  2. 时间复杂度:
    • 迪杰斯特拉算法:具有较高的效率,时间复杂度为O(V^2)(使用朴素实现)或O((V+E) log V)(使用优先队列优化)。(V顶点E条边)
    • 弗洛伊德算法:时间复杂度为O(V^3),因为它需要计算所有顶点对的最短路径。
  3. 实现方式:
    • 迪杰斯特拉算法:通常使用贪心策略,从一个顶点开始,逐步扩展到邻接顶点,直到找到所有顶点的最短路径。
    • 弗洛伊德算法:使用动态规划,通过三层循环迭代地改进路径长度,直到达到最优解。
  4. 对负权边的处理:
    • 迪杰斯特拉算法:不能处理负权边,因为负权边会破坏算法的贪心选择性质。
    • 弗洛伊德算法:可以处理负权边,但图中不能有负权环,否则最短路径问题没有解。
  5. 初始化:
    • 迪杰斯特拉算法:从源点到其他所有顶点的距离初始化为无穷大,源点到自身的距离为0。
    • 弗洛伊德算法:所有顶点到自身的距离初始化为0,其他顶点间的距离初始化为边的权重或无穷大(如果无直接连接)。

本篇详解Floyd算法,如果想看Dijkstra算法的话,可以看博主上一篇博客,针对于Dijkstra算法的详解:迪杰斯特拉(Dijkstra)算法(C/C++)-CSDN博客

执笔至此,感触彼多,全文将至,落笔为终,感谢大家的支持。  

这篇关于弗洛伊德(Floyd)算法(C/C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1115513

相关文章

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

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

康拓展开(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]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

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

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

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

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

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

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

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名