c++中如何实现Floyd算法_c++ Floyd算法实现方法

尼克

发布时间：2025-10-01 19:44:02

1013人浏览过

来源于php中文网

原创

Floyd算法通过动态规划求解所有顶点对间最短路径，核心是三重循环松弛操作，时间复杂度O(n³)，适用于小规模图且可处理负权边。

c++中如何实现floyd算法_c++ floyd算法实现方法

在C++中实现Floyd算法（也称Floyd-Warshall算法）用于求解图中所有顶点对之间的最短路径。该算法适用于带权有向图或无向图，能处理负权边（但不能有负权环）。核心思想是动态规划，通过中间节点逐步更新最短路径。

算法基本原理

Floyd算法基于这样一个事实：如果从顶点i到j的最短路径经过某个中间顶点k，那么这条路径可以拆分为i到k和k到j的两段最短路径。通过枚举所有可能的中间点k，不断松弛任意两点间的距离。

设dist[i][j]表示从顶点i到j的当前最短距离，初始时为图的邻接矩阵。算法进行如下更新：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

立即学习“C++免费学习笔记（深入）”；

MD5校验和计算小程序（C）

C编写，实现字符串摘要、文件摘要两个功能。里面主要包含3个文件: Md5.cpp、Md5.h、Main.cpp。其中Md5.cpp是算法的代码，里的代码大多是从 rfc-1321 里copy过来的；Main.cpp是主程序。

下载

实现步骤

以下是具体的实现流程：

初始化一个二维数组dist，大小为n×n（n为顶点数），表示任意两点间的距离
若i==j，则dist[i][j]为0；若i与j之间有边，则赋值为对应权重；否则设为一个极大值（如INT_MAX/2）
三重循环：外层枚举中间点k，内层枚举起点i和终点j，尝试通过k更新i到j的距离
最终dist[i][j]即为i到j的最短路径长度

C++代码示例

下面是一个完整的C++实现：

#include 
#include 
#include 
using namespace std;

const int INF = INT_MAX / 2; // 防止加法溢出

void floyd(vector>& 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++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // 输出结果
    cout << "最短路径矩阵：" << endl;
    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;
    }
}

int main() {
    int n = 4;
    vector> graph = {
        {0,   3,   INF, 7},
        {8,   0,   2,   INF},
        {5,   INF, 0,   1},
        {2,   INF, INF, 0}
    };

    floyd(graph);
    return 0;
}

注意事项

使用Floyd算法时需注意以下几点：

INF值不宜取INT_MAX，避免后续加法导致整数溢出，建议用INT_MAX/2
算法时间复杂度为O(n³)，适合顶点数较少的图（一般n ≤ 500）
空间复杂度为O(n²)，需要存储整个距离矩阵
若需记录路径，可额外维护一个parent[i][j]数组，在更新距离时同步更新前驱节点

基本上就这些。Floyd算法实现简洁，适合多源最短路径问题，理解其状态转移逻辑是关键。

C++如何实现一个A*寻路算法？C++游戏AI与路径规划【算法实战】

c++在Unreal Engine中的应用_c++ UE4/5游戏开发基础

如何用C++实现一个有限状态机（FSM）？C++游戏AI与协议解析【设计模式】

c++如何实现一个简单的神经网络推理框架_c++ ONNX Runtime集成【AI】

c++如何使用TensorRT进行模型部署优化_c++ NVIDIA推理引擎入门【AI】

c++速学教程(入门到精通)

c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

ai c++ ios stream 循环算法

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：c++中如何使用结构体_c++结构体使用方法下一篇：c++字符串和数字之间如何转换_c++字符串数字转换方法

作者最新文章

Linux怎么查看内存使用 Linux查询内存剩余及占用分析【详解】

2026-01-26 09:10

MAC怎么设置程序全屏_MAC窗口全屏与退出全屏快捷键【小白入门】

2026-01-26 09:19

c++中如何生成随机数_c++ rand与srand用法【指南】

2026-01-26 09:19

iphone日历总有垃圾广告怎么办_苹果手机清除日历弹窗【清理】

2026-01-26 09:21

iQOO手机怎么开启双WiFi加速_iQOO网络加速设置教程【诀窍】

2026-01-26 09:23

BIOS设置丢失？CMOS电池耗尽或重置异常【配置还原】

2026-01-26 09:24

OPPO手机充电慢是怎么回事 OPPO手机无法快充的原因与解决办法【一文搞懂】

2026-01-26 09:27

C++怎么保留两位小数 C++控制输出精度iomanip使用教程【格式】

2026-01-26 09:31

Linux怎么统计文件行数 Linux计算文件字数wc命令用法【技巧】

2026-01-26 09:41

电脑怎么禁止程序联网？在电脑防火墙中设置应用访问权限【教程】

2026-01-26 09:43

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI 编程开发 AI 聊天问答

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI 编程开发 AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI 编程开发 Agent智能体

腾讯元宝

腾讯混元平台推出的AI助手

文档处理 AI 聊天问答

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI 编程开发 AI 文本写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

AI 文本写作中文写作

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI 编程开发 AI 文本写作

智谱清言 - 免费全能的AI助手

AI 编程开发 Agent智能体

相关专题

页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章，大家可以免费体验。

407

2023.08.14

俄罗斯Yandex引擎入口

2026年俄罗斯Yandex搜索引擎最新入口汇总，涵盖免登录、多语言支持、无广告视频播放及本地化服务等核心功能。阅读专题下面的文章了解更多详细内容。

2026.01.28

包子漫画在线官方入口大全

本合集汇总了包子漫画2026最新官方在线观看入口，涵盖备用域名、正版无广告链接及多端适配地址，助你畅享12700+高清漫画资源。阅读专题下面的文章了解更多详细内容。

2026.01.28

ao3中文版官网地址大全

AO3最新中文版官网入口合集，汇总2026年主站及国内优化镜像链接，支持简体中文界面、无广告阅读与多设备同步。阅读专题下面的文章了解更多详细内容。

2026.01.28

php怎么写接口教程

本合集涵盖PHP接口开发基础、RESTful API设计、数据交互与安全处理等实用教程，助你快速掌握PHP接口编写技巧。阅读专题下面的文章了解更多详细内容。

2026.01.28

php中文乱码如何解决

本文整理了php中文乱码如何解决及解决方法,阅读节专题下面的文章了解更多详细内容。

2026.01.28

Java 消息队列与异步架构实战

本专题系统讲解 Java 在消息队列与异步系统架构中的核心应用，涵盖消息队列基本原理、Kafka 与 RabbitMQ 的使用场景对比、生产者与消费者模型、消息可靠性与顺序性保障、重复消费与幂等处理，以及在高并发系统中的异步解耦设计。通过实战案例，帮助学习者掌握使用 Java 构建高吞吐、高可靠异步消息系统的完整思路。

2026.01.28

Python 自然语言处理（NLP）基础与实战

本专题系统讲解 Python 在自然语言处理（NLP）领域的基础方法与实战应用，涵盖文本预处理（分词、去停用词）、词性标注、命名实体识别、关键词提取、情感分析，以及常用 NLP 库（NLTK、spaCy）的核心用法。通过真实文本案例，帮助学习者掌握使用 Python 进行文本分析与语言数据处理的完整流程，适用于内容分析、舆情监测与智能文本应用场景。

2026.01.27