弗洛伊德算法求最短路径

### Floyd-Warshall算法简介

Floyd-Warshall算法是一种用于计算加权图中所有顶点对之间最短路径的经典动态规划方法[^2]。该算法不仅能够处理单源最短路径问题，还能解决多源最短路径问题，即找出每一对不同节点间的最短距离。

此算法特别适用于稠密图以及存在负权重边的情况（只要不存在总长度为负数的环）。对于含有V个顶点的图而言，时间复杂度为O(V³)，空间复杂度同样为O(V²)。

### 算法原理说明

核心思想在于逐步增加中间节点k来优化当前已知的最佳路径矩阵D(k)[i][j]：

- 初始化阶段设置直接相连两点间的真实代价作为初始估计值；
- 对于每一个可能充当中介角色的节点k，在考虑通过它连接其他任意两节点(i,j)之前先保存现有最优解d_old=d[i][j];
- 如果经过第k个节点可以使得从i到j更近，则更新d_new=min(d_old,d[i][k]+d[k][j])并记录下来；

最终得到的结果表就包含了整个网络里任何位置相互到达所需的最小开销。

### Python实现示例

下面给出一段简单的Python代码用来展示如何利用上述逻辑构建完整的解决方案:

def floyd_warshall(graph):
    V = len(graph)
    
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
  
    for k in range(V): 
        for i in range(V): 
            for j in range(V): 
                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
                
    return dist 

# Example usage:
INF = float('inf')
graph = [
          [0, 7, INF, 8],
          [INF, 0, 5, INF],
          [INF, INF, 0, 2],
          [INF, INF, INF, 0]
        ]
result = floyd_warshall(graph)

for row in result:
    print(row)

这段程序定义了一个名为`floyd_warshall()`的功能函数接收邻接矩阵形式表示的一张有向带权图，并返回一个新的二维数组代表各点之间的最短路程。注意这里使用了无穷大(INF)标记那些不可达的位置。