FloydWarshall 图论

### Floyd-Warshall算法在图论中的解释与应用

#### 算法概述
Floyd-Warshall算法是一种用于计算加权有向图中所有顶点对之间的最短路径的经典动态规划方法[^3]。该算法特别适用于稠密图，即边的数量接近于节点数量平方的情况。

#### 工作原理
此算法通过逐步改进路径长度来工作。对于每一对顶点(i,j)，考虑每一个其他顶点k作为中间点，并尝试更新i到j的距离为更小值——如果经过k到达会更快的话。这个过程重复进行直到不再有任何改善为止。

#### 时间复杂度分析
时间复杂度为O(n^3)，其中n表示图中的顶点数。这是因为三重循环遍历了所有的可能组合[(i, j), k]来进行距离矩阵的更新操作。

#### 实现示例
下面是一个简单的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

在这个例子中`graph`应该被定义成一个二维列表形式的邻接矩阵，其中无穷大代表两个节点间不存在直接连接。

#### 应用场景
除了基本的最短路径查找外，Floyd-Warshall还可以用来解决一些变种问题，比如寻找具有最小邻居的城市等问题[^5]。此外，在某些情况下也可以扩展其功能以处理负权重环检测等高级特性。