- 1
- 2
- 3
- 4
- 5
Floyd-Warshall算法
资料介绍
一、算法概述
Floyd-Warshall算法是一种用于求解图中所有顶点间最短路径的动态规划算法，由Robert Floyd于1962年提出，其思想源自Stephen Warshall在1962年发表的求传递闭包的算法。该算法能够处理带权有向图或无向图，包括含有负权边的情况，但不能处理包含负权回路的图（因为负权回路会导致路径长度无限减小）。算法的时间复杂度为O(n³)，其中n为图中顶点的数量，空间复杂度为O(n²)，适用于中等规模的图计算。
二、基本原理
（一）核心思想
算法基于动态规划的思想，通过逐步引入中间顶点来更新任意两点间的最短路径。具体而言，设d[k][i][j]表示从顶点i到顶点j，且中间顶点仅允许使用集合{1, 2, ..., k}时的最短路径长度。其状态转移方程如下：
d[k][i][j] = min
其中，d[0][i][j]为初始状态，即图的邻接矩阵：若i和j直接相连，则为边的权值；若i=j，则为0；否则为无穷大（表示不可达）。
（二）空间优化
由于计算d[k][i][j]仅依赖于d[k-1][...]，因此可使用二维数组替代三维数组，通过原地更新实现空间优化，此时状态转移方程简化为：
d[i][j] = min
部分文件列表
| 文件名 | 大小 |
| Floyd-Warshall算法.docx | 19K |
最新上传
- 打赏
- 30日榜单
-
21ic下载 打赏310.00元 1天前
用户：江岚
-
21ic下载 打赏310.00元 1天前
用户：mulanhk
-
21ic下载 打赏320.00元 1天前
用户：jh03551
-
21ic下载 打赏220.00元 1天前
用户：jh0355
-
21ic下载 打赏210.00元 1天前
用户：潇潇江南
-
21ic下载 打赏210.00元 1天前
用户：小猫做电路
-
21ic下载 打赏60.00元 1天前
用户：gsy幸运
-
21ic下载 打赏60.00元 1天前
用户：zhengdai
-
21ic下载 打赏60.00元 1天前
用户：lanmukk
-
21ic下载 打赏60.00元 1天前
用户：烟雨
-
21ic下载 打赏20.00元 1天前
用户：w993263495
-
21ic下载 打赏30.00元 1天前
用户：sun2152
-
21ic下载 打赏20.00元 1天前
用户：w178191520
-
21ic下载 打赏20.00元 1天前
用户：liqiang9090
-
21ic下载 打赏20.00元 1天前
用户：xuzhen1
-
21ic下载 打赏35.00元 1天前
用户：有理想666
-
21ic下载 打赏15.00元 1天前
用户：w1966891335
-
21ic下载 打赏15.00元 1天前
用户：x15580286248
-
21ic下载 打赏25.00元 1天前
用户：qiufeng0299
-
21ic下载 打赏15.00元 1天前
用户：kk1957135547
-
21ic下载 打赏10.00元 1天前
用户：qingsong08
-
21ic下载 打赏10.00元 1天前
用户：电工老刘
-
21ic小能手 打赏5.00元 2天前
-
21ic小能手 打赏5.00元 2天前
-
21ic小能手 打赏5.00元 2天前
-
ZENGYIBIN 打赏1.00元 3天前
-
21ic小能手 打赏10.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
资料：STM32的数字万用表
-
21ic小能手 打赏5.00元 3天前
-
kuangwy 打赏1.00元 3天前
-
21ic小能手 打赏5.00元 3天前
资料：触控无极台灯控制方案
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
资料：51单片机的汽车雨刷器
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
-
21ic小能手 打赏5.00元 3天前
全部评论(0)