弗洛伊德-沃肖尔算法

### Floyd-Warshall算法概述

Floyd-Warshall算法是一种用于计算加权图中所有顶点对之间的最短路径的经典动态规划方法[^1]。该算法适用于带权重的有向图或无向图，但不支持含有负权重环路的情况。

#### 算法原理

核心思想在于逐步更新每一对节点间的距离矩阵。对于每一个可能经过的中间节点k，检查通过此节点到达另一端是否会更优；如果确实如此，则更新相应的最短路径长度。具体来说：

- 初始化阶段设置邻接矩阵D(0)，其中d[i][j]=w(i,j)表示直接连接i到j边上的权重；
- 对于每一层迭代l=1,...,|V|-1，构建新的距离矩阵D(l)=min{D(l−1), D(l−1)[i,k]+D(l−1)[k,j]}，这里k代表当前考虑作为中介点的顶点编号。

这种逐层优化的方式使得最终得到的距离表包含了任意两点间最优解的信息。

def floyd_warshall(graph):
    V = len(graph)
    
    dist = list(map(lambda i : 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

上述代码实现了基本版的Floyd-Warshall算法，输入参数`graph`是一个二维列表形式表示的有权重图，输出则是同样结构化的最短路径距离表格。

#### 应用场景

由于能够一次性求得整个网络内所有的两两节点间最小代价通路，因此非常适合应用于通信网络设计、交通流量分析以及社交关系挖掘等多个方面。特别是在那些需要频繁查询不同位置之间最佳路线的应用场合下表现出色[^2]。