宛蛲 发表于 2025-9-26 19:03:29

浅谈Floyd算法

弗洛伊德算法是用于求解无负权回路的图的任意一对顶点间最短路径的算法，该算法采用的基本思想是动态规划（转移方程就是cost = cost + cost < cost ? cost + cost : cost）
算法步骤：令初始邻接矩阵matrix[][]为cost[][]，对于每个顶点k，检查以此为中转顶点，对每对顶点i和j，若cost + cost < cost则更新cost = cost + cost，并且同时记录下这个中转的顶点k于path中，检查完每个顶点即可
代码如下
// 复用数据结构邻接矩阵，见 https://www.cnblogs.com/RodneyTang/p/19010305void floyd(adjMaxtrix &mGraph, int **&path, int **&cost){    path = (int **)malloc(sizeof(int *) * mGraph.vnum);    cost = (int **)malloc(sizeof(int *) * mGraph.vnum);    for (int i = 0; i < mGraph.vnum; ++i)      path = (int *)malloc(sizeof(int) * mGraph.vnum);    for (int i = 0; i < mGraph.vnum; ++i)      for (int j = 0; j < mGraph.vnum; ++j)      {            path = -1;            cost = mGraph.matrix;      }    for (int k = 0; k < mGraph.vnum; ++k)      for (int i = 0; i < mGraph.vnum; ++i)            for (int j = 0; j < mGraph.vnum; ++j)                if (cost... -> k ... -> v，这样递归地查找和的中间顶点即可，规定path = -1时无中间顶点，即路径是i -> j</p>这个算法的时空复杂度都很显然，不必多说

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

时思美 发表于 2025-10-28 04:13:22

新版吗？好像是停更了吧。

怃膝镁 发表于 2025-12-11 01:33:37

这个有用。

郗燕岚 发表于 2026-1-15 11:55:11

过来提前占个楼

呈步 发表于 2026-1-15 23:26:26

yyds。多谢分享

呵桢 发表于 2026-1-18 22:03:25

喜欢鼓捣这些软件，现在用得少，谢谢分享！

蓬庄静 发表于 2026-1-19 23:57:30

yyds。多谢分享

喳谍 发表于 2026-1-19 23:57:36

感谢分享，学习下。

时思美 发表于 2026-1-21 08:13:06

用心讨论，共获提升！

坟菊 发表于 2026-1-22 11:30:25

感谢分享，学习下。

劳暄美 发表于 2026-1-22 18:31:38

感谢分享，学习下。

郗新语 发表于 2026-1-22 21:30:35

这个有用。

威割 发表于 2026-1-23 17:37:25

喜欢鼓捣这些软件，现在用得少，谢谢分享！

梭净挟 发表于 2026-1-25 09:16:57

前排留名，哈哈哈

绘纵 发表于 2026-1-26 01:00:37

前排留名，哈哈哈

鞣谘坡 发表于 2026-1-29 06:52:58

谢谢分享，辛苦了

窟聿湎 发表于 2026-1-30 05:34:54

很好很强大我过来先占个楼 待编辑

汇干环 发表于 2026-2-3 20:46:17

过来提前占个楼

毋峻舷 发表于 2026-2-8 09:16:34

很好很强大我过来先占个楼 待编辑

洪势 发表于 2026-2-9 08:50:14

分享、互助 让互联网精神温暖你我
页: [1] 2
查看完整版本: 浅谈Floyd算法