首页
▼ 算法合集
▼ 加密算法
▼ 凯撒密码
凯撒密码
▼ Hill密码算法
Hill密码算法
▼ 多项式哈希算法
多项式哈希算法
▼ Rail Fence Cipher
Rail Fence Cipher
▼ Graph算法
▼ 关节点
关节点
▼ Bellman-Ford算法
Bellman-Ford算法
▼ 广度优先搜索
广度优先搜索
▼ GraphBridges
桥接模式
▼ 深度优先搜索
深度优先搜索
▼ 检测循环
检测循环
▼ Dijkstra算法
Dijkstra算法
▼ Eulerian Path
欧拉路径
▼ Floyd-Warshall算法
Floyd-Warshall算法
▼ HamiltonianCycle
Hamiltonian Cycle
▼ Kruskal算法
Kruskal算法
▼ Prim算法
Prim算法
▼ 强连通分量
强连通分量
▼ 拓扑排序
拓扑排序
▼ Travelling Salesman Problem
Travelling Salesman
▼ 图像处理算法
▼ Seam Carving算法
内容感知缩放算法
▼ 链表
▼ 反向遍历
反向遍历
▼ GraphTraversal
GraphTraversal
▼ 数学算法
▼ 二进制浮点数
BinaryFloatingPoint
▼ 位操作
位操作算法
▼ 复数
复数
▼ 欧几里得算法
Euclidean Algorithm
▼ Euclidean Distance
欧几里得距离
▼ 阶乘算法
阶乘算法
▼ 快速幂算法
快速幂算法
▼ Fibonacci数列
斐波那契数列
▼ 傅里叶变换
Fourier变换
▼ Horner法
霍纳法则
▼ 整数划分
整数划分
▼ 判断是否为2的幂
判断是否为2的幂
▼ 最小公倍数
最小公倍数
▼ Liu Hui
Liu Hui
▼ 矩阵
Matrix
▼ Pascal三角形
Pascal三角形
▼ Primality Test
素数测试
▼ 质因数
质因数
▼ 弧度计算
弧度计算
▼ 埃拉托色尼筛法
埃拉托色尼筛法
▼ SquareRoot
SquareRoot
▼ MachineLearning
▼ K均值算法
K均值算法
▼ K近邻算法
K近邻算法
▼ 搜索算法
▼ 二分查找算法
二分查找
▼ 插值搜索算法
插值搜索算法
▼ 跳跃搜索算法
跳跃搜索算法
▼ 线性搜索
线性搜索算法
▼ 集合
▼ 笛卡尔积
笛卡尔积
▼ 组合总和
组合总和
▼ 组合算法
组合算法
▼ Fisher-Yates洗牌算法
Fisher-Yates洗牌算法
▼ 背包问题
背包问题
▼ 最长公共子序列
最长公共子序列
▼ 最长递增子序列
最长递增子序列
▼ 最大子数组
最大子数组
▼ 排列组合
排列组合
▼ 幂集
幂集算法
▼ 最短公共超序列
最短公共超序列
▼ Sorting Algorithms
▼ 冒泡排序
冒泡排序
▼ 桶排序算法
桶排序算法
▼ 计数排序算法
计数排序
▼ 堆排序算法
堆排序
▼ 插入排序
插入排序
▼ 归并排序
归并排序
▼ 快速排序算法
快速排序算法
▼ 基数排序
基数排序
▼ 选择排序算法
选择排序算法
▼ 希尔排序
希尔排序
▼ 统计学
▼ 加权随机
加权随机算法
▼ 字符串算法
▼ Hamming距离
Hamming距离
▼ KnuthMorrisPratt算法
Knuth-Morris-Pratt算法
▼ LevenshteinDistance
Levenshtein距离
▼ 最长公共子串
最长公共子串
▼ 回文检测算法
回文检测算法
▼ Rabin-Karp算法
Rabin-Karp算法
▼ 正则表达式匹配
正则表达式匹配
▼ Z算法
Z算法
▼ Tree Data Structure
▼ 广度优先搜索
广度优先搜索
▼ 深度优先搜索
深度优先搜索
▼ 未分类
▼ 最佳买卖股票时机
最佳买卖股票时机
▼ 汉诺塔算法
HanoiTower
▼ 跳跃游戏算法
跳跃游戏
▼ KnightTour
骑士巡逻
▼ N皇后问题
N皇后问题
▼ 雨水收集
雨水收集
▼ 递归楼梯问题
递归楼梯问题
▼ 方阵旋转
方阵旋转
▼ 独特路径
UniquePaths
▼ 数据结构
▼ BloomFilter算法
布隆过滤器
▼ 不相交集数据结构
Disjoint Set
▼ 双向链表
双向链表
▼ Graph
Graph算法
▼ 哈希表
哈希表
▼ Heap数据结构
Heap数据结构
▼ 链表
链表
▼ LRU缓存
LRU缓存
▼ 优先队列
优先队列
▼ 队列
队列
▼ 栈结构
栈结构
▼ Tree Data Structure
树结构
▼ AVL树
AVL树
▼ 二叉搜索树
二叉搜索树
▼ Fenwick树
Fenwick树
▼ 红黑树
红黑树
▼ 线段树
SegmentTree
▼ Trie数据结构
Trie数据结构
弗洛伊德-沃沙尔算法
在计算机科学中，弗洛伊德-沃沙尔算法是一种用于查找具有正数或负边权重的带权图中最短路径的算法（但不包括负环）。该算法的单次执行将找到图中所有顶点对之间的最短路径长度（加权和）。尽管它不会返回路径本身的详细信息，但可以通过简单的修改算法来重建路径。
算法
弗洛伊德-沃沙尔算法通过比较图中每对顶点之间可能的所有路径来工作。它能够在图中使用O(|V|^3)次比较完成。考虑到图中可能有最多|V|^2条边，并且测试了每条边的所有组合，这确实非常令人印象深刻。它是通过逐步改进两个顶点之间最短路径的估计值来完成的，直到估计值是最优的。
考虑一个顶点集为V编号从1到N的图G。进一步考虑一个函数shortestPath(i, j, k)，它返回从i到j的最短可能路径，使用的是仅来自集合{1, 2, ..., k}的顶点作为中间点。现在，根据这个函数，我们的目标是仅使用集合{1, 2, ..., N}中的顶点找到从每个i到每个j的最短路径。
这个公式是弗洛伊德-沃沙尔算法的核心。
示例
上述算法在下面的左侧图上执行：
在下方的表格中，i是行号，j是列号。
k = 0
|
1 |
2 |
3 |
4 |
| 1 |
0 |
∞ |
−2 |
∞ |
| 2 |
4 |
0 |
3 |
∞ |
| 3 |
∞ |
∞ |
0 |
2 |
| 4 |
∞ |
−1 |
∞ |
0 |
k = 1
|
1 |
2 |
3 |
4 |
| 1 |
0 |
∞ |
−2 |
∞ |
| 2 |
4 |
0 |
2 |
∞ |
| 3 |
∞ |
∞ |
0 |
2 |
| 4 |
∞ |
− |
∞ |
0 |
k = 2
|
1 |
2 |
3 |
4 |
| 1 |
0 |
∞ |
−2 |
∞ |
| 2 |
4 |
0 |
2 |
∞ |
| 3 |
∞ |
∞ |
0 |
2 |
| 4 |
3 |
−1 |
1 |
0 |
k = 3
|
1 |
2 |
3 |
4 |
| 1 |
0 |
∞ |
−2 |
0 |
| 2 |
4 |
0 |
2 |
4 |
| 3 |
∞ |
∞ |
0 |
2 |
| 4 |
3 |
−1 |
1 |
0 |
k = 4
|
1 |
2 |
3 |
4 |
| 1 |
0 |
−1 |
−2 |
0 |
| 2 |
4 |
0 |
2 |
4 |
| 3 |
5 |
1 |
0 |
2 |
| 4 |
3 |
−1 |
1 |
0 |
参考文献