floyd算法求最短路径伪代码

Floyd-Warshall算法是一种用于求解有向图或无向图中所有顶点对之间最短路径的经典动态规划方法。以下是算法的伪代码：

// 初始化距离矩阵 dist，其中 dist[i][j] 存储从 i 到 j 的最短路径
for i in 0...n:
    for j in 0...n:
        if i == j:
            dist[i][j] = 0 // 起点到起点的距离总是0
        else:
            dist[i][j] = inf // 使用极大值初始化，表示无穷大

// 遍历所有节点对 (i, k) 和 (k, j)，更新最短路径
for k in 0...n:
    for i in 0...n:
        for j in 0...n:
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

// 返回最终距离矩阵 dist，dist[i][j] 就是最短路径

在这个伪代码中，`n` 表示图中的顶点数，`inf` 代表无穷大，初始状态下每个节点到其他节点都是无穷远。通过三重循环不断检查是否存在经过某个中间节点k能够缩短路径的情况，最终得到的是每一对顶点之间的最短路径。