在计算机科学中，Floyd-Warshall算法是一种在具有正或负边权重的加权图中寻找最短路径的算法。该算法的一次执行将找到所有顶点对之间最短路径的长度。虽然它不返回路径本身的细节，但是可以通过简单地修改算法来重构路径。该算法的版本还可用于寻找关系R的传递闭包或加权图中所有顶点对之间的最宽路径。

弗洛伊德-沃肖尔算法是动态规划的一个例子，由罗伯特·弗洛伊德于1962年发表。但它与1959年以前发表的Bernard Roy算法和1962年发现的史蒂芬·沃舍尔传递闭包基本相同，与克莱尼算法密切相关，后者用于将确定性有限自动机转化为正则表达式。作为三个嵌套循环的现代公式，该算法最早是由彼得·英格曼在1962年描述的。

该算法也称为弗洛伊德算法、罗伊-沃肖尔算法、罗伊-弗洛伊德算法或WFI算法。

优点和缺点:

弗洛伊德算法适用于动态规划算法APSP。密集图效果最好，边权重可以为正，也可以为负。该算法简单有效。由于三重循环的紧凑结构，稠密图的效率高于具有|V|倍的Dijkstra算法。

优点:易于理解，可以计算任意两个节点之间的最短距离，代码编写简单

缺点:时间复杂度比较高，不适合计算大量数据。

时间复杂度:o；空之间的复杂度:o；

从任意节点I到j的最短路径有两种可能性:

直接从I到J；

我穿过几个节点k到j。

Map表示从节点I到j的最短路径距离，对于每个节点k，检查map+map是否小于map。如果是真的，map = map+map；；遍历每k个，每次更新第k行和第k列以外的数字。

Floyd 第一迭代 弗洛伊德，第一次迭代

Floyd 第二迭代 弗洛伊德，第二次迭代

Floyd 第三迭代 弗洛伊德，第三次迭代

让我们试着解决以下问题: