多源最短路径算法

要解决多源最短路径问题，我们有两种方法，一是对每一个顶点进行单源最短路径算法，二是利用弗洛伊德算法解决。在这里我们了解弗洛伊德算法的实现过程。

弗洛伊德算法利用一个矩阵，矩阵的元素代表两个节点之间的最短距离，如果两个节点没有直接相连，那么对角线上的初始值就赋值为正无穷，否则就是两个节点间的边长值。然后我们依次加入图中的顶点进行计算，加入顶点$v_0$时，我们对图进行遍历，检查$D[i][k]+D[k][j]<D[i][j]$是否成立，如果成立，那么更新$D[i][j]=D[i][k]+D[k][j]$,因为$i$到$k$的距离和$j$到$k$的在有向图中不一定相等，所以我们必须遍历整个图来完成，代码的具体实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void Floyd(){
    for(i=0;i<N;++i){
        for(j=0;j<N;++j){
            D[i][j]=G[i][j];
        }
    }
    for(k=0;k<N;++k){
        for(i=0;i<N;++i){
            for(j=0;j<N;++j){
                if(D[i][k]+D[k][j]<D[i][j]){
                    D[i][j]=D[i][k]+D[k][j];
                }
            }
        }
    }
}