知道了单源最短路的算法之后，我们可以更进一步，学习多源最短路问题，因为我们的需求是多样的，我们在知道某点到某点最短距离之后还想知道其他两点间的最短距离，那么我们需要再求解一次吗？显然，那样过于麻烦，显然，我们需要一种算法来一次性求解所有的两两间距，用的时候只需要取出即可

弗洛伊德（Floyd）算法

弗洛伊德算法是比较经典的求解多元路径的算法，代码极为简洁

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef int Pathmatirx[MAXSIZE][MAXSIZE];
typedef int ShortPathTable[MAXSIZE][MAXSIZE];

void ShortestPathFloyd(MGraph graph, Pathmatirx *P, ShortPathTable *D){
    int v, w, k;
    for (v = 0; v < graph->nv; ++v)
        for (w = 0; w < graph->nv; ++w) {	// 初始化数组
            (*D)[v][w] = graph->g[v][w];
            (*P)[v][w] = w;
        }
    for (k = 0; k < graph->nv; ++k)
        for (v = 0; v < graph->nv; ++v)
            for (w = 0; w < graph->nv; ++w)
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]){	// 求解
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    (*P)[v][w] = (*P)[v][k];
                }
}

算法解释：

  • 首先对传入的两个二维数组进行初始化，将图的存储权重的数组复制给D数组，P数组将每列初始化为列标数
  • 利用三重循环来查找最短路径
    • k控制中转点，如：k = 0时，所有顶点都经过v0中转；k = 1时，所有顶点都经过v1中转......
    • 依次判断两个点经过中转点时路径是否会缩短，如果是，更新D数组的权重，P数组相应位置更新为中转点的下标
  • 所以，最后结果为D数组存着某点到某点的最短距离的值，P数组存着相应的某两点之间最短路径所经过的中转点

细节说明：

  • 上述代码直接适用于邻接矩阵存储的图，如是邻接表存储，则初始化部分的代码需重写
1
2
typedef int Pathmatirx[MAXSIZE][MAXSIZE];
typedef int ShortPathTable[MAXSIZE][MAXSIZE];
  • 以上述方式定义之后便于直接将二维数组以参数传递进函数
  • 判断的代码直接带入图中更好理解：v -> w 的距离是否大于v->k 再由 k->w的距离之和，以此种方式更容易理解和记忆写出该代码的方树，k是中转点也变得更容易理解

输出结果

运行算法之后，该如何输出某点到某点的最短路径呢？我们直接给出最普遍的方式——打印出所有两两结点间的最短路径

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
for (v = 0; v < graph->nv; ++v) {
    for (w = v+1; w < graph->nv; ++w) {
        printf("v%d-v%d weight:%d", v, w, (*D)[v][w]);
        k = (*P)[v][w];
        printf(" path: %d", v);
        while (k != w){
            printf(" -> %d", k);
            k = (*P)[k][w];
        }
        printf(" -> %d\n", w);
    }
    printf("\n");
}

算法解释：

  • 首先输出某点到某点以及之间的距离
  • 之后输出路径
    • 在P数组对应位置找到其值k，输出该值之后让其代替初始结点（v）下标
    • 在新的位置找到新的k并赋值，输出，直至 k==w

说明：

该循环直接嵌入上述函数使用