C/C++环境下的弗洛伊德算法实现详解

C/C++环境下弗洛伊德算法实现深度剖析

弗洛伊德算法(Floyd's algorithm),也被称作弗洛伊德-沃尔什算法(Floyd-Warshall algorithm),是一种用于在加权图中探寻所有顶点对之间最短路径的算法。该算法适用于有向图与无向图,能够处理负权重边,但无法应对负权重循环。

弗洛伊德算法(Floyd-Warshall Algorithm)属于一种用于计算图中所有顶点对之间最短路径的动态规划算法。本文将会细致地讲解弗洛伊德算法的原理,并提供一个C++实现的示例,以此助力读者领会算法的运作原理以及编程技巧。

算法原理

弗洛伊德算法的核心思路是通过逐步探寻并更新所有顶点对之间的最短路径来解决问题。算法借助一个距离矩阵来存储顶点之间的距离,并且在每一步骤中会考虑通过一个新的中间顶点来更新这些距离。和之前介绍的Dijkstra算法原理类似,都是借助中转点来更新最短距离。不过,弗洛伊德算法处理的是多源的最短路问题。

算法步骤

  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])

弗洛伊德是典型的三重for循环,所以其时间复杂度为O(n^3),这里的n是图中顶点的数量。第一层循环遍历中转点,第二层循环遍历起点,第三层循环遍历终点,对于图中点数量较多的情况,弗洛伊德算法的时间复杂度相对较高。

图解算法:

接下来我们以一个包含4个点的图来进行讲解,图中的边是有向边和无向边的结合。以邻接矩阵的方式进行存储,要是大家偏好用邻接表存储,也可以采用邻接表。下面介绍两个矩阵,矩阵A表示(i,j)i到j的最短距离,初始化为无穷大。矩阵B表示i到j路径中除去起点的第一个中转点,初始化为-1。

初始状态:

依据图中的点之间的距离进行赋值,矩阵A中i到i的距离都为0,无穷大表示无法到达。矩阵B初始化为-1。

第一步:

选取一个点(按顺序选取)作为中转点,查看以它作为中转点时,能否使所到达的点产生更小的距离,如果产生了,就更新矩阵A的距离以及矩阵B的中转点。我们先选取1号点,那么位于1号点的行和列的值不会发生变化,自身到自身的点距离永远是0,图中黄色标记的是此步不会改变的点,其他点可能会变化。在更新距离时无需看图也能更新矩阵,例如图中2号点到3号点原本距离为10,以1号点作为中转点,路径为2 - 1 - 3,此时距离为2 + 6 = 8 < 10,通过1号点绕路的方式距离更短。类似地,3到2号点、3到4号点、4到3号点等也会有相应更新。同时更新矩阵B。

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

第二步:

把2号结点当作中转结点,查看能够更新哪些最短路径,和上一步一样直接看图更新。比如4到1号点,距离为2 + 4 = 6 < 10;1到4号点,距离为2 + 4 = 6 < 10;3到4号点,距离为8 + 4 = 12 < 16等。对于一些无法更新的值,例如1到3号点,2 + 8 = 10 > 6,就不进行更新。

对于矩阵B,要注意3到4和4到3的路径相反,更新时3到4号点的第一个中转点还是1号点。更新后(红色标记为变化的值):

第三步:

把3号点作为中转结点,像前几步一样继续寻找最短距离。经过更新发现3号点作为中转点无法更新任何距离,所以矩阵A、B不需要更新。在图中验证可知3号点中转距离反而变大,因此不更新。

第四步:

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

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

算法实现:

以下是弗洛伊德算法的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; // 自己到自己的距离是0
        for (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. 迪杰斯特拉算法:主要用于单元路径的最短路问题,也就是从单一源点到所有其他顶点的最短路径。

  3. 弗洛伊德算法:解决的是所有顶点对之间的最短路径问题,即计算图中每一对顶点之间的最短路径。
  4. 时间复杂度:
  5. 迪杰斯特拉算法:具有较高的效率,时间复杂度为O(V^2)(使用朴素实现)或O((V+E) log V)(使用优先队列优化)。(V为顶点数,E为边数)

  6. 弗洛伊德算法:时间复杂度为O(V^3),因为它需要计算所有顶点对的最短路径。
  7. 实现方式:
  8. 迪杰斯特拉算法:通常采用贪心策略,从一个顶点出发,逐步扩展到邻接顶点,直至找到所有顶点的最短路径。

  9. 弗洛伊德算法:运用动态规划,通过三层循环迭代地改进路径长度,直到达到最优解。
  10. 对负权边的处理:
  11. 迪杰斯特拉算法:无法处理负权边,因为负权边会破坏算法的贪心选择性质。

  12. 弗洛伊德算法:可以处理负权边,但图中不能存在负权环,否则最短路径问题无解。
  13. 初始化:
  14. 迪杰斯特拉算法:从源点到其他所有顶点的距离初始化为无穷大,源点到自身的距离为0。

  15. 弗洛伊德算法:所有顶点到自身的距离初始化为0,其他顶点间的距离初始化为边的权重或无穷大(如果无直接连接)。

本篇对弗洛伊德算法进行了详细剖析,如果想要了解迪杰斯特拉算法,可以查看博主的上一篇博客,其中有针对迪杰斯特拉算法的详细讲解:迪杰斯特拉(Dijkstra)算法(C/C++)-CSDN博客

至此,全文即将结束,感谢大家的支持。

文章整理自互联网,只做测试使用。发布者:Lomu,转转请注明出处:https://www.it1024doc.com/12780.html

(0)
LomuLomu
上一篇 12小时前
下一篇 10小时前

相关推荐

  • 履约系统:应用层、领域层、集成关系设计

    大家好,我是汤师爷~ 在这篇文章中,我们一起探讨订单履约系统的应用架构设计。 应用架构设计 我们前面讨论了系统的核心概念模型和拆单逻辑。接下来,让我们从应用架构的角度,深入了解系统的各个层次。这包括应用层、领域层,以及与其他系统的集成关系。 应用层能力 应用层定义软件的应用功能,它负责接收用户请求,协调领域层能力来执行任务,并将结果返回给用户,核心模块包括:…

    2025 年 1 月 1 日
    21600
  • Java实现数据库图片上传(包含从数据库拿图片传递前端渲染)-图文详解

    目录 1、前言: 2、数据库搭建 : 建表语句: 3、后端实现,将图片存储进数据库: 思想: 找到图片位置(如下图操作) 图片转为Fileinputstream流的工具类(可直接copy) 存储数据库 mapper层: service层: control层: 4、后端实现,从数据库取出图片给前端(可直接看这个,这个给的是所有代码) dao层: mapper层…

    2025 年 1 月 21 日
    29300
  • 🚀 2025年最新IDEA激活码分享 | 永久破解IDEA终极教程(支持2099年)

    💻 适用Jetbrains全家桶(IDEA/PyCharm/DataGrip等) 先给大家看看最新版IDEA成功破解到2099年的效果图,是不是很诱人?😍 本教程将手把手教你如何永久激活IDEA,方法同样适用于旧版本!无论你是Windows、Mac还是Linux系统,统统适用~ 📥 下载IDEA安装包 如果已经安装可以跳过这步哦! 访问官网:https://…

    2025 年 6 月 8 日
    44600
  • 『玩转Streamlit』–集成定时任务

    学习了Streamlit了之后,可以尝试给自己的命令行小工具加一个简单的界面。 本篇总结了我改造自己的数据采集的工具时的一些经验。 1. 概要 与常规的程序相比,数据采集任务的特点很明显,比如它一般都是I/O密集型程序,涉及大量网络请求或文件读写,耗费的时间比较长;而且往往是按照一定的时间间隔周期性地执行。 这样的程序对交互性要求不高,所以我之前都是用命令行…

    2025 年 1 月 12 日
    34600
  • 2025年最新DataGrip激活码与永久破解教程 🔥 附注册码及破解方法

    2025年最新DataGrip激活码与永久破解教程 🔥 附注册码及破解方法 在使用DataGrip进行数据库开发时,很多小伙伴可能会遇到需要激活码的情况😅。本文将为大家详细介绍如何获取最新的DataGrip激活码,以及一些破解方法,但请注意,我们更推荐使用正版软件哦✨! DataGrip激活码获取方法 首先,我们可以尝试通过JetBrains官网获取官方的D…

    DataGrip破解教程 2025 年 5 月 19 日
    22000

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息

关注微信