多源最短路径

多源最短路不是“多个起点一起跑”，而是要得到任意两点之间的最短距离；这通常意味着你要维护一整张距离矩阵。

核心概念

多源最短路径：求所有顶点对之间的最短路径。

Floyd-Warshall算法：

• 时间复杂度：O(V³)
• 空间复杂度：O(V²)
• 适用：稠密图、所有点对最短路径

为什么一般想到 Floyd-Warshall

因为它最适合回答这种问题：

我不是只关心一个起点，而是关心任意 i 到任意 j 的最短路。

如果把单源最短路算法重复跑很多次当然也能做，但当图规模不大、问题就是“全对全”时，Floyd-Warshall 的矩阵写法更直接。

经典应用

算法特点

优点：

• 简洁易懂，代码短
• 能处理负权边（但不能有负环）
• 一次计算得到所有点对最短路径

缺点：

• 时间复杂度高O(V³)
• 不适合大规模稀疏图

使用场景：

• 图的规模较小（V < 500）
• 需要所有点对的最短路径
• 图比较稠密

Go 代码

func floydWarshall(graph [][]int) [][]int {
    n := len(graph)
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, n)
        copy(dist[i], graph[i])
    }
 
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }
 
    return dist
}

易错点

多源最短路最容易错的地方，不是三重循环，而是初始化和无穷大处理。

• dist[i][i] 必须初始化为 0。
• 不连通边要统一初始化成足够大的 inf。
• 做加法前要先判断两段是不是都可达，避免 inf + inf 这类溢出逻辑。
• 如果图很稀疏、点很多，O(V^3) 往往不现实。

---

返回：图算法