最短路径算法Floyed

### Floyd-Warshall 最短路径算法原理

Floyd-Warshall算法是一种用于解决多源最短路径问题的经典动态规划方法。该算法能够有效地找出带权重有向图中任意两点间的最短路径，即使存在负权边也能正常工作，不过遇到负环则会失效[^1]。

核心在于迭代地增加可作为中介点的顶点集，在每次循环过程中尝试利用新增加的那个顶点优化当前已知的最佳路径长度。具体来说就是对于每一个可能成为中间站的节点k，检查并更新其他任何两个不同端点i和j之间是否存在更优解——即经过k之后总路程变得更短的情况；如果确实如此，则替换旧记录为新发现的距离值[^3]。

递推关系表达如下：

\[ d[i][j]=\min(d[i][j],d[i][k]+d[k][j]) \]

这里\(d[i][j]\)表示从起点i到达终点j所花费的成本（可以理解成距离），而上述公式的意义是在考察是否能通过某个特定位置k使得原本连接ij这条线路变得更加经济实惠一些。

### 实现代码示例

以下是Python版本的Floyd-Warshall算法实现方式：

def floyd_warshall(graph):
    V = len(graph)
    
    dist = list(map(lambda i : list(map(lambda j : j , i)) , graph))
  
    for k in range(V): 
  
        # pick all vertices as source one by one 
        for i in range(V): 
  
            # Pick all vertices as destination for the above picked source 
            for j in range(V): 
                dist[i][j] = min(dist[i][j] ,dist[i][k]+ dist[k][j])
                
    return dist

此函数接收一个二维列表形式输入参数`graph`,其中每个元素代表对应索引编号间直接相连时所需支付费用(如果是无穷大意味着这两点并不相通)，最终返回相同规格矩阵对象`dist`保存着各组起始坐标至目标坐标的最小消耗量度信息[^2]。