数据结构(17)-图之最短路径

我们经常会面临对路径选择的问题，比如出行去某个地方，如何乘车路线最短等。其实这就是图的最短路径问题。对于非网图而言，由于边没有权值，最短路劲就是指两顶点之间经过的边数最少的路径，可以直接使用广度遍历算法逐层遍历得到最短路径。对于网图而言，最短路径是指两个顶点之间经过的边上权值之和最少的路径，一般地，我们称路径上第一个顶点为源点，最后一个顶点为终点。下面我们来看两种计算最短路径的方法。

迪杰斯特拉算法`(Dijkstra)`

迪杰斯特拉算法的核心思想是按照路径长度递增的次序产生最短路径。我们借助一个例子来看看其计算过程：

迪杰斯特拉算法示例.png

从 $v_0$ 出发，找到到下一个顶点的最短距离即为 $v_1$ ；由于 $v_1$ 的邻接点是 $v_2$ 、 $v_3$ 、 $v_4$ ， $v_0$ 到 $v_2$ 的最短距离则是 $v_0$ -> $v_1$ -> $v_2$ ，为1+3=4； $v_2$ 的邻接点 $v_4$ 、 $v_5$ ， $v_0$ -> $v_2$ -> $v_4$ 为4+1=5，比 $v_0$ -> $v_2$ -> $v_5$ 为4+7=11，所以下一个顶点为 $v_4$ ； $v_0$ -> $v_1$ -> $v_4$ 为1+5=6，所以从 $v_0$ 到 $v_4$ 最短的路径是5。以此类推，从 $v_0$ 到 $v_8$ 的最短距离是 $v_0$ -> $v_1$ -> $v_2$ -> $v_4$ -> $v_3$ -> $v_6$ -> $v_7$ -> $v_8$ ，结果为1+3+1+2+3+2+4=16。

那上述过程如何用代码实现呢？我们需要用一个数组来标记从源点到某个顶点是否已经求得了最短路径；还需要一个数组记录从源点到某个顶点的路径权值；另外还需要一个数组来记录当前顶点的前驱顶点的下标。

// 用于存储最短路径前驱顶点下标的数组
typedef int Patharc[MAX_VEX_COUNT];
// 用于存储到各点最短路径权值的和
typedef int ShortPathTable[MAX_VEX_COUNT];

void dijkstraShortestPath(MGraph graph, int v0, Patharc *parcIndexes, ShortPathTable *spWeights) {
    // 标记顶点是否被加入到最小路径中
    int finals[MAX_VEX_COUNT] = {0};
    
    // 设置源点的数据 邻接点的权值等
    for (int i = 0; i < graph.vertexNum; i++) {
        (* parcIndexes)[i] = 0;
        (* spWeights)[i] = graph.arc[0][i];
    }
    
    // 设置v0到v0之间数据
    finals[v0] = 1;
    (* parcIndexes)[v0] = -1;
    (* spWeights)[v0] = 0;
    
    
    // 最小权值
    int minWeight = INT_INFINITY;
    int minIndex = 0;
    for (int i = 0; i < graph.vertexNum; i++) {
        if (i == v0) {
            // 源点已加入到路径中
            continue;
        }
        
        minWeight = INT_INFINITY;
        
        // 遍历 找到i的邻接顶点中权值最小的顶点
        for (int j = 0; j < graph.vertexNum; j++) {
            if (!finals[j] && (* spWeights)[j] < minWeight) {
                minIndex = j;
                minWeight = (* spWeights)[j];
            }
        }
        
        printf("最小权值%d-下标%d\n", minWeight, minIndex);
        finals[minIndex] = 1;
        
        // 更新下一个顶点的相关信息 即得到从v0到minIndex顶点的邻接点的权值之和 这样就可以在下次比较中选择出minIndex之后顶点
        // 对比从v0直接到顶点k的权值 和 从v0到minIndex然后再到顶点k的路径权值
        // 如果存在其他路径权值更小 修正对应的权值用来作为下次比较使用
        for (int k = 0; k < graph.vertexNum; k++) {
            if (!finals[k] && (minWeight + graph.arc[minIndex][k] < (* spWeights)[k])) {
                (* spWeights)[k] = minWeight + graph.arc[minIndex][k];
                (* parcIndexes)[k] = minIndex;
            }
        }
    }
}

控制台输出：

最小权值1-下标1
最小权值4-下标2
最小权值5-下标4
最小权值7-下标3
最小权值8-下标5
最小权值10-下标6
最小权值12-下标7
最小权值16-下标8

迪杰斯特拉算法比较难以理解的就是对spWeights和parcIndexes数组进行更新的部分，比如我们从示例中的 $v_0$ 开始，第一轮比较得到minWeight = 1， minIndex = 1，选中的顶点是 $v_1$ ，在更新代码中k = 2，此时spWeights[2] = 5，而我们从 $v_0$ 到 $v_1$ 再到 $v_2$ 的权值是4，4 < 5，更新spWeights[2] = 4。以此类推，得到spWeights[3] = 8、spWeights[4] = 6。下一轮i = 2的比较时，直接就可以得出minWeight = 4， minIndex = 2。

由代码可以看出， $m$ 个顶点， $n$ 条边，迪杰斯特拉算法的时间复杂度为 $O(n^2)$ 。而且很明显，迪杰斯特拉算法是一个单源算法，也就是我们需要指定一个源点和终点。而我们如果需要整个图各种顶点之间的最短路径，就需要再来 $m$ 。下面我们来看一种多源的算法。

弗洛伊德算法`(floyd)`

弗洛伊德算法是一种多源算法，他解决了整个图中，所有顶点之间的最短路径。他的核心思想是一个公式：

$D^0[v][w] = min\{D^{-1}[v][w], D^{-1}[v][k]+D^{-1}[k][w] \}$

这个公式主要是借助于一个中转顶点 $k$ 来实现，在判断某两个顶点之间的权值是不是最小路径权值的时候，通过引入中转顶点，互相对比判断得出最小的路径的权值。

弗洛伊德算法示例.png

通过图，可以看到，弗洛伊德算法引入了两个二维数组，第一个数组的作用是保存就每个顶点之间的最短路径权值之和，第二个数组的作用是保存顶点之间最短路径所经过的顶点。下面我们结合代码来看看弗洛伊德算法公式的具体含义及作用。

// 存放顶点之间最短路径的权值
typedef int ShortestWeights[MAX_VEX_COUNT][MAX_VEX_COUNT];

// 存放顶点之间最短路径经过的顶点
typedef int ShortestVertexes[MAX_VEX_COUNT][MAX_VEX_COUNT];

void floydShortestPath(MGraph graph, ShortestWeights *sWeights, ShortestVertexes *sVertexes) {
    // 初始化条件
    for (int i = 0; i < graph.vertexNum; i++) {
        for (int j = 0; j < graph.vertexNum; j++) {
            (* sWeights)[i][j] = graph.arc[i][j];
            (* sVertexes)[i][j] = j;
        }
    }
    
    for (int k = 0; k < graph.vertexNum; k++) {
        for (int i = 0; i < graph.vertexNum; i++) {
            for (int j = 0; j < graph.vertexNum; j++) {
                // 如果经过下标为k的顶点路径比原来两顶点之间的路径更短 则需要修改原来两顶点之间的权值
                if ((* sWeights)[i][j] > (* sWeights)[i][k] + (* sWeights)[k][j]) {
                    (* sWeights)[i][j] = (* sWeights)[i][k] + (* sWeights)[k][j];
                    (* sVertexes)[i][j] = (* sVertexes)[i][k];
                }
            }
        }
    }
}

void floydTest() {
    MGraph graph;
    createMgraphForDijkstra(&graph);
    
    ShortestWeights sWeights;
    ShortestVertexes sVertexes;
    
    floydShortestPath(graph, &sWeights, &sVertexes);
    
    int vertex = 0;
    for (int i = 0; i < graph.vertexNum; i++) {
        for (int j = i+1; j < graph.vertexNum; j++) {
            printf("(v%d-v%d) weight:%d path: %d", i, j, sWeights[i][j], i);
            vertex = sVertexes[i][j];
            
            while (vertex != j) {
                printf(" -> %d", vertex);
                vertex = sVertexes[vertex][j];
            }
            printf(" -> %d\n", j);
        }
        printf("\n");
    }
}

控制台输出：

(v0-v1) weight:1 path: 0 -> 1
(v0-v2) weight:4 path: 0 -> 1 -> 2
(v0-v3) weight:7 path: 0 -> 1 -> 2 -> 4 -> 3
(v0-v4) weight:5 path: 0 -> 1 -> 2 -> 4
(v0-v5) weight:8 path: 0 -> 1 -> 2 -> 4 -> 5
(v0-v6) weight:10 path: 0 -> 1 -> 2 -> 4 -> 3 -> 6
(v0-v7) weight:12 path: 0 -> 1 -> 2 -> 4 -> 3 -> 6 -> 7
(v0-v8) weight:16 path: 0 -> 1 -> 2 -> 4 -> 3 -> 6 -> 7 -> 8

(v1-v2) weight:3 path: 1 -> 2
(v1-v3) weight:6 path: 1 -> 2 -> 4 -> 3
(v1-v4) weight:4 path: 1 -> 2 -> 4
(v1-v5) weight:7 path: 1 -> 2 -> 4 -> 5
(v1-v6) weight:9 path: 1 -> 2 -> 4 -> 3 -> 6
(v1-v7) weight:11 path: 1 -> 2 -> 4 -> 3 -> 6 -> 7
(v1-v8) weight:15 path: 1 -> 2 -> 4 -> 3 -> 6 -> 7 -> 8

(v2-v3) weight:3 path: 2 -> 4 -> 3
(v2-v4) weight:1 path: 2 -> 4
(v2-v5) weight:4 path: 2 -> 4 -> 5
(v2-v6) weight:6 path: 2 -> 4 -> 3 -> 6
(v2-v7) weight:8 path: 2 -> 4 -> 3 -> 6 -> 7
(v2-v8) weight:12 path: 2 -> 4 -> 3 -> 6 -> 7 -> 8

(v3-v4) weight:2 path: 3 -> 4
(v3-v5) weight:5 path: 3 -> 4 -> 5
(v3-v6) weight:3 path: 3 -> 6
(v3-v7) weight:5 path: 3 -> 6 -> 7
(v3-v8) weight:9 path: 3 -> 6 -> 7 -> 8

(v4-v5) weight:3 path: 4 -> 5
(v4-v6) weight:5 path: 4 -> 3 -> 6
(v4-v7) weight:7 path: 4 -> 3 -> 6 -> 7
(v4-v8) weight:11 path: 4 -> 3 -> 6 -> 7 -> 8

(v5-v6) weight:7 path: 5 -> 7 -> 6
(v5-v7) weight:5 path: 5 -> 7
(v5-v8) weight:9 path: 5 -> 7 -> 8

(v6-v7) weight:2 path: 6 -> 7
(v6-v8) weight:6 path: 6 -> 7 -> 8

(v7-v8) weight:4 path: 7 -> 8

通过代码可以看出，弗洛伊德算法的非常简单精妙，就是通过三层遍历，然后不断的修正最小路径权值。虽说其时间复杂度为 $O(n^3)$ ，但是依然不妨碍其成为一个优秀的算法。

参考文献：

大话数据结构

数据结构(17)-图之最短路径

迪杰斯特拉算法(Dijkstra)

弗洛伊德算法(floyd)

迪杰斯特拉算法`(Dijkstra)`

弗洛伊德算法`(floyd)`