最短路径问题

最短路径问题：如果从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和（称为路径长度）达到最小。

单源最短路径问题：计算从源点到其他所有顶点的最短路径长度。

多源最短路径问题：计算从所有顶点到所有顶点的最短路径长度。

Floyd算法

Floyd-Warshall 算法：又称为插点法，是一种利用动态规划的思想求多源最短路径的算法。

图中可以有正权边或负权边，但是不能有负权回路。

算法思想：

g[a][b]:当前已知从 a 到 b 的最短路径长度。

状态定义：g[k][i][j]：只能使用第1号到第k号点作为中间媒介时，点i到点j之间的最短路径长度。

初始条件：如果存在弧，g[0][i][j] = w(i, j) i到j弧的权值如果不存在弧，g[0][i][j] = INF

状态转移方程：g[k][i][j]=min(g[k?1][i][j],g[k?1][i][k]+g[k?1][k][j])

数组降维：g[i][j]=min(g[i][j],g[i][k]+g[k][j])

如果 g[1][3]>g[1][2]+g[2][3]

那么 g[1][3]=g[1][2]+g[2][3]

for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

Floyed的时间复杂度是 O(N3??)

算法图解

建立邻接矩阵