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
上一篇 10小时前
下一篇 8小时前

相关推荐

  • 2024 IDEA最新激活码,IDEA永久免费激活码2025-01-12 更新

    IDEA 2024最新激活码 以下是最新的IDEA激活码,更新时间:2025-01-12 🔑 激活码使用说明 1️⃣ 复制下方激活码 2️⃣ 打开 IDEA 软件 3️⃣ 在菜单栏中选择 Help -> Register 4️⃣ 选择 Activation Code 5️⃣ 粘贴激活码,点击 Activate ⚠️ 必看!必看! 🔥 获取最新激活码: 实时更…

    2025 年 1 月 12 日
    75800
  • 微软开源!Office 文档轻松转 Markdown!

    大家好,我是 Java陈序员。 今天,给大家介绍一款微软开源的文档转 Markdown 工具。 关注微信公众号:【Java陈序员】,获取开源项目分享、AI副业分享、超200本经典计算机电子书籍等。 项目介绍 MarkItDown —— 微软开源的 Python 工具,能够将多种常见的文件格式(如 PDF、PowerPoint、Word、Excel、图像、音频…

    2025 年 1 月 12 日
    35000
  • RabbitMQ消息中间件核心概念与实践指南

    RabbitMQ概述 RabbitMQ是一款采用Erlang编程语言构建的开源消息代理软件,其官方网站为:RabbitMQ官方平台。本文将深入解析其核心架构原理与基础应用方法。 环境部署 部署过程中需要关注两个关键端口配置:* 15672:管理控制台的访问入口* 5672:消息传输处理接口完成安装后,通过http://127.0.0.1:15672即可访问管…

    2025 年 5 月 11 日
    16600
  • Bolt.new 30秒做了一个网站,还能自动部署,难道要吊打 Cursor?

    大家好,我是汤师爷~ 这篇聊聊 Bolt.new 和 Cursor 的对比。 Bolt.new 是一款基于 SaaS 的 AI 编码平台。它由 LLM 驱动的智能体作为底层,并结合 WebContainers 技术,让用户可以直接在浏览器中进行编码和运行。其主要优势包括: 支持前后端同时开发; 项目文件夹结构可视化; 环境自托管,自动安装依赖(如 Vite、…

    2025 年 1 月 10 日
    27900
  • 开启AI大模型应用开发新篇:LangChain打造RAG增强检索生成

    开启AI大模型应用开发的新篇章:LangChain助力RAG增强检索生成 检索增强生成(RAG)是一种将“向量检索”和“大语言模型”相结合的技术途径,能在问答、摘要、文档分析等场景中极大提升准确性与上下文的利用率。 本文将基于 LangChain 构建完整的 RAG 流程,结合 PGVector 作为向量数据库,并用 LangGraph 构建状态图来控制流程…

    2025 年 6 月 23 日
    4000

发表回复

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

联系我们

400-800-8888

在线咨询: QQ交谈

邮件:admin@example.com

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

关注微信