图的应用 - 最短路径

定义

简而言之，最短路径就是找图中连接两个顶点所有边权重和最小的路径

• 如果给定起点，则是单源最短路径，即从一个固定起点到任意终点的最短路径
• 如果起点不确定，则是多源最短路径，即任意两个顶点的最短路径

基础概念

源点与终点

路径起始的第一个顶点称为源点，最后一个顶点成为终点

最短路径

无权图

对于无权图而言，从源点$V_0$到终点$V_8$的最短路径就是从源点$V_0$到终点$V_8$所包含的边最少的路径。只需要从源点$V_0$出发对图进行广度优先搜索，一旦遇到终点$V_8$就终止。

思路

1. 遍历顶点$V_0$
2. 遍历顶点$V_0$的邻接顶点$V_1$和$V_2$（具体的操作可以使用队列来实现）
3. 遍历顶点$V_1$的邻接顶点$V_3$和$V_4$，遍历顶点$V_2$的邻接顶点$V_5$
4. 遍历顶点$V_3$的邻接顶点$V_6$，遍历顶点$V_4$的邻接顶点$V_7$
5. 遍历顶点$V_6$的邻接顶点$V_8$，正好是终点

由此，可以得到，从源点$V_0$到终点$V_8$的最短路径（其中之一）：$V_0->V_1->V_3->V_6->V_8$

有权图

对于有权图来说，最短路径的求解需要使用Dijkstra算法，即算法会求得从一个指定源点到终点的权重和最小的最短路径。

由此，从源点 $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

Dijkstra算法

首先，引进一个辅助向量D，它的每一个分量 $D[i]$表示 当前所找到的从源点 $v$到每一个顶点 $v_i$的最短路径的长度。

它的初态为：若从 $v$到 $v_i$有弧（边），则 $D[i]$为弧上的权值；否则 $D[i]$为无穷（INF）。

显然，长度为 $$ D[j]=Min_j{D[i]v_i \in V} $$ 的路径就是从 $v$出发的长度最短的一条最短路径。此路径为 $(v_i, v_j)$。

算法流程

1. 将所有的顶点分为两部分：

   • 已知最短路径的顶点集合 D
   • 未知最短路径的顶点集合 Q

   最开始，已知最短路径的顶点集合 D 中只有源点 s 一个顶点，在这用 final[i]数组来记录哪些点在集合 D 中。

   例如对于某个顶点 i，如果final[i] = 1 则表示这个顶点在集合 D 中，否则表示在集合 Q 中

2. 设置源点 s 到自己最短路径为0 即 dist = 0。把源点不邻接的所有顶点的最短路径设为无穷

3. 在 Q 中选择一个离源点最近的顶点 u 加入到 D中，同时将以 u 为起点的边，对每一个条边进行松弛操作，并将 final[v] = 1

4. 重复第 3 步操作，如果 Q 为空，算法结束。最终 dist 数组中的值就是源点到所有顶点的最短路径

算法图解

1. 初始化辅助向量 D, 路径向量 P 和当前已求得顶点$V_0$到$V_j$的最短路径的向量 Final

   • 辅助向量 D 的初态：若从$V_0$到$V_j$有弧，则 D[j] 为弧上的权值；否则 D[j] 为无穷

2. 遍历源点$V_0$，找到源点$V_0$的邻接顶点中距离最短的顶点，即$V_1$，$V_0$到$V_1$的最短路径为 1 已经求出，更新 Fina[1] = 1

3. 遍历顶点$V_1$，找到顶点$V_1$的邻接顶点$V_0$、$V_2$、$V_3$、$V_4$（其中$V_0$已经加入了最短路径中，不需要考虑）
   • 从$V_1$到$V_2$的距离是 3，所以$V_0$到$V_2$的距离是 1 + 3 = 4，小于辅助向量 D 中的距离 5，则更新 D[2] = 4
   • 从$V_1$到$V_3$的距离是 7，所以$V_0$到$V_3$的距离是 1 + 7 = 8，小于辅助向量 中的 D[3]，则更新 D[3] = 8
   • 从$V_1$到$V_4$的距离是 5，所以$V_0$到$V_4$的距离是 1 + 5 = 6，小于辅助向量 中的 D[4]，则更新 D[4] = 6
   • 相应的将顶点$V_2$、$V_3$、$V_4$的前驱结点更新为$V_1$的下标 1
4. 重复 2 、3 步骤

5. 遍历源点$V_0$，找到从源点$V_0$出发距离最短的且 Final[i] = 0的顶点，为$V_2$，则更新Final[2] = 1

6. 遍历顶点$V_2$并更新辅助向量 D 和路径向量 P
7. 重复操作，找到从源点$V_0$出发距离最短的且 Final = 0 的顶点，为$V_8$，更新 Final[8] = 1，算法执行结束

根据路径向量 P，可以得到$V_0$到$V_8$的最短路径为：$V_0->V_1->V_2->V_4->V_3->V_6->V_7->V_8$

权重和为：16

代码实现

typedef int  Patharc[MAXVEX]; // 用于存储最短路径下标的数组
typedef int  ShortPathTable[MAXVEX]; // 用于存储到各点最短路径的权值和
void Dijkstra(GNode G, int v0, Patharc *P, ShortPathTable *D) {
    int Final[MAXVEX] = {0};
    memset(P, 0, sizeof(int) * MAXVEX);
    
    // 初始化辅助数组D
    int v;
    for (v = 0; v < G.Nv; v++) {
        (*D)[v] = G.arc[v0][v];
    }
    // 源点为 0，加入到最短路径中
    Final[v0] = 1;
    (*P)[v0] = -1;
    // min
    int min;
    int k = 0, w;
    for (v = 1; v < G.Nv; v++) {
         min = MAX_INT;
        // 找到权重最小的邻接顶点
        for (w = 0; w < G.Nv; w++) {
            if (!Final[w] && (*D)[w] < min) {
                k = w;
                min = (*D)[w];
            }
        }
        
        Final[k] = 1;
        //
        
        for (w = 0; w < G.Nv; w++) {
            if (!Final[w] && (min + G.arc[k][w]) < (*D)[w]) {
                (*D)[w] = min + G.arc[k][w];
                (*P)[w] = k;
            }
        }
    }
}

Floyd算法

Floyd算法是一个经典的动态规划算法。其主要思路为：从任意顶点u 到任意顶点v 的最短路径不外乎两种可能

• 直接从 u 到 v
• 从 u 经过若干个顶点 k 到 v

所以，我们假设dist(u，v) 为顶点u 到顶点v 的最短路径的距离，对于每一个顶点 k，我们检查 dist(u，k) + disk(k，v) < disk(u, v)是否成立，若干成立，证明从 u 到 k 再到 v 的路径比 u 直接到 v 的路径短，我们便设置disk(u, v) = dist(u，k) + disk(k，v)

这样当我们遍历完所有顶点 k，dist(u，v)中记录的便 u 到 v 的最短路径的距离。

算法流程

1. 从任意一条单边路径开始。所有两点之间的距离是边的权值，如果两点之间没有变相连，则权为无穷大
2. 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果有，则更新

算法图解

1. 选取单边路径$V_0->V_1$，由于$V_0->V_1$的距离为 1
2. 遍历剩余顶点 $V_2、V_3、V_4、V_5、V_6、V_7、V_8$，寻找是否有可以选做中间站的顶点，使得顶点 0 到顶点 1 路径小于 1
3. 遍历完所有顶点，没有找到比顶点$V_0->V_1$的路径，因此，$V_0->V_1$是顶点 0 到顶 1 的最短路径， 不存在中转顶点
4. 遍历剩余顶点寻找$V_1->V_2$的中间顶点，同样，不存在中转顶点，$V_1->V_2$是顶点 1 到 2 的最短路径，以此类推

当选取顶点 0 为源点，顶点 3 为终点时

1. 顶点 0 与顶点 3 不邻接，因此距离为无穷
2. 顶点 1 与顶点 2 可以通过顶点 1 中转，经过中转后的距离为 4，此时的路径为 $V_0->V_1->V_2$
3. 顶点 2 与顶点 3 可以通过顶点 4 中转，经过中转后的距离为 3，此时的路径为 $V_2->V_4->V_3$
4. 因此，顶点 0 到顶点 3 的最短路径为：$V_0->V_1->V_2->V_4->V_3$

代码实现

typedef int Parent[MAXVEX][MAXVEX];
typedef int Dist[MAXVEX][MAXVEX];

void floyd(GNode G, Dist *dist, Parent *parent) {
    
    // 初始化
    int v, w;
    for (v = 0; v < G.Nv; v++) {
        for (w = 0; w < G.Nv; w++) {
            (*dist)[v][w] = G.arc[v][w];
            (*parent)[v][w] = w;
        }
    }
    
    // k 表示经过的中转顶点
    int k;
    for (k = 0; k < G.Nv; k++) {
        for (v = 0; v < G.Nv; v++) {
            for (w = 0; w < G.Nv; w++) {
                if ((*dist)[v][w] > (*dist)[v][k] + (*dist)[k][w]) {
                    (*dist)[v][w] = (*dist)[v][k] + (*dist)[k][w];
                    (*parent)[v][w] = (*parent)[v][k];
                }
            }
        }
    }
}

完整代码

总结

最短路径问题是图论研究中的一个经典算法问题。因此针对图最短路径问题先后提出了许多算法。各类算法的应用场景不尽相同。Dijkstra算法和Bellman-Ford算法用于解决单源最短路径，而Floyd算法可以解决多源最短路径。

Dijkstra算法适用稠密图（邻接矩阵），因为稠密图问题与顶点关系密切。Bellman-Ford算法算法适用稀疏图（邻接表），因为稀疏图问题与边关系密切。 Floyd算法在稠密图（邻接矩阵）和稀疏图（邻接表）中都可以使用。