【图的应用二：最短路径】- 用 C 语言实现迪杰斯特拉算法和弗洛伊德算法

目录

一、最短路径

二、迪杰斯特拉算法

三、弗洛伊德算法

---

 

---

一、最短路径

假若要在计算机上建立一个交通咨询系统，则可以采用图的结构来表示实际的交通网络。如下图所示，图中顶点表示城市，边表示城市间的交通联系。

这个咨询系统可以回答旅客提出的各种问题。例如，一位旅客要从 A 城到 B 城，他希望选择一条中转次数最少的路线。假设图中每一站都需要换车，则这个问题反映到图上就是找一条顶点 A 到顶点 B 所包含边的数目最少的路径。只需从顶点 A 出发对图做广度优先搜索，一旦遇到顶点 B 就终止，由此所得的广度优先生成树上，从根顶点 A 到顶点 B 的路径就是中转次数最少的路径。

但是，这只是一类最简单的图的最短路径问题。有时，对于旅客来说，可能更关心的是节省交通费用；而对于司机来说，里程和速度则是他们感兴趣的信息。为了在图上表示有关信息，可对边赋予权，权的值表示两城市间的距离，或途中所需时间，或交通费用等。此时路径长度的度量就不再是路径上边的数目，而是路径上边的权值之和。考虑到交通图的有向性，例如，汽车的上山和下山，轮船的顺水和逆水，所花费的时间或代价就不相同，所以交通网往往是用带权有向网表示。在带权有向网中，习惯上称路径上的第一个顶点为源点（Source），最后一个顶点为终点（Destination）。

下面主要讨论两种最常见的最短路径问题：一种是求从某个源点到其余各顶点的最短路径，另一种是求每一对顶点之间的最短路径。

---

二、迪杰斯特拉算法

单源点的最短路径问题：给定带权有向图 G 和源点 v0，求从 v0 到 G 中其余各顶点的最短路径。

迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法，称为迪杰斯特拉算法。

(1) 迪杰斯特拉算法的求解过程：

对于网 N = (V, E)，将 N 中的顶点分为两组：

第一组 S：已求出的最短路径的终点集合（初始时只包含源点 v0）。

第二组 V - S：尚未求出的最短路径的顶点集合（初始时为 V - {v0}）。

算法将按各顶点与 v0 间最短路径长度递增的次序，逐个将集合 V - S 中的顶点加入到集合 S 中去。在这个过程中，总保持从 v0 到集合 S 中各顶点的路径长度始终不大于到集合 V - S 中各顶点的路径长度。

这种求解方法能确保是正确的，因为假设 S 为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为 x）或是边 (v0, x)，或是中间只是经过 S 中的顶点而最后到达顶点 x 的路径。

这可用反证法来证明。假设此路径上有一个顶点不在 S 中，则说明存在一条终点不在 S 而长度比此路径短的路径。但是，这是不可能的，因为算法是按路径长度递增的次序来产生最短路径的，故长度比此路径短的所有路径均已产生，它们的终点必定在 S 中，即假设不成立。

(2) 迪杰斯特拉算法的实现：

假设用带权的邻接矩阵 arcs 来表示带权有向网 G。

算法的实现要引入以下辅助的数据结构：

1. 一维数组 S[i]：记录从源点 v0 到终点 vi 是否已被确定最短路径长度，true 表示确定，false 表示尚未确定。

2. 一维数组 Path[i]：记录从源点 v0 到终点 vi 的当前最短路径上 vi 的直接前驱顶点序号。其初值为：如果从 v0 到 vi 有弧，则 Path[i] 为 v0；否则为 -1。

3. 一维数组 D[i]：记录从源点 v0 到终点 vi 的当前最短路径长度。其初值为：如果从 v0 到 vi 有弧，则 D[i] 为弧上的权值；否则为 。

   最短路径为 D[k] = Min{ D[i] | }，求得从源点到 vk 的最短路径后，将 vk 加入到第一组顶点集 S 中。

   每当加入一个新的顶点到顶点集 S，对第二组剩余的各个顶点而言，多了一个 "中转" 顶点，从而多了一个 "中转" 路径，所以要对第二组剩余的各个顶点的最短路径长度进行更新。

   原来从 v0 到 vi 的最短路径长度为 D[i]，加入 vk 之和，以 vk 作为中间顶点的 "中转" 路径长度为：D[k] + G.arcs[k][i]，若 D[k] + G.arcs[k][i] < D[i]，则用 D[k] + G.arcs[k][i] < D[i] 取代 D[i]。

AMGraph.h：

#pragma once
​
typedef char VertexType;
typedef int ArcType;
​
#define DEFAULT_CAPACITY 2
​
typedef struct AMGraph
{VertexType* vertices;ArcType** arcs;int vSize;int aSize;int capacity;
}AMGraph;
​
void AMGraphInit(AMGraph* pg);
​
void ShowAdjMatrix(AMGraph* pg);
​
int GetVertexPos(AMGraph* pg, VertexType v);
​
void InsertVertex(AMGraph* pg, VertexType v);
void InsertArc(AMGraph* pg, VertexType v1, VertexType v2, ArcType cost);
​
// 迪杰斯特拉算法
void ShortestPath_DIJ(AMGraph* pg, VertexType v, int* D, int* Path);

AMGraph.c：

#include "AMGraph.h"
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
​
void AMGraphInit(AMGraph* pg)
{assert(pg);pg->vSize = pg->aSize = 0;pg->capacity = DEFAULT_CAPACITY;
​pg->vertices = (VertexType*)malloc(sizeof(VertexType) * pg->capacity);assert(pg->vertices);
​pg->arcs = (ArcType**)malloc(sizeof(ArcType*) * pg->capacity);assert(pg->arcs);for (int i = 0; i < pg->capacity; ++i){pg->arcs[i] = (ArcType*)malloc(sizeof(ArcType) * pg->capacity);assert(pg->arcs[i]);for (int j = 0; j < pg->capacity; ++j){if (i == j)pg->arcs[i][j] = 0;elsepg->arcs[i][j] = INT_MAX;}}
}
​
void ShowAdjMatrix(AMGraph* pg)
{assert(pg);printf("   ");  // 输出 3 个空格for (int i = 0; i < pg->vSize; ++i){printf("%c  ", pg->vertices[i]);}printf("\n");
​for (int i = 0; i < pg->vSize; ++i){printf("%c  ", pg->vertices[i]);for (int j = 0; j < pg->vSize; ++j){if (pg->arcs[i][j] == INT_MAX)printf("#  ");  // 用 # 代替 ∞elseprintf("%-3d", pg->arcs[i][j]);}printf("\n");}
}
​
int GetVertexPos(AMGraph* pg, VertexType v)
{assert(pg);for (int i = 0; i < pg->vSize; ++i){if (pg->vertices[i] == v)return i;}return -1;
}
​
void InsertVertex(AMGraph* pg, VertexType v)
{assert(pg);// 考虑是否需要扩容if (pg->vSize == pg->capacity){VertexType* tmp1 = (VertexType*)realloc(pg->vertices, sizeof(VertexType) * 2 * pg->capacity);assert(tmp1);pg->vertices = tmp1;
​ArcType** tmp2 = (ArcType**)realloc(pg->arcs, sizeof(ArcType*) * 2 * pg->capacity);assert(tmp2);pg->arcs = tmp2;for (int i = 0; i < pg->capacity; ++i){ArcType* tmp3 = (ArcType*)realloc(pg->arcs[i], sizeof(ArcType) * 2 * pg->capacity);assert(tmp3);pg->arcs[i] = tmp3;for (int j = pg->capacity; j < 2 * pg->capacity; ++j){pg->arcs[i][j] = INT_MAX;}}for (int i = pg->capacity; i < 2 * pg->capacity; ++i){pg->arcs[i] = (ArcType*)malloc(sizeof(ArcType) * 2 * pg->capacity);assert(pg->arcs[i]);for (int j = 0; j < 2 * pg->capacity; ++j){if (i == j)pg->arcs[i][j] = 0;elsepg->arcs[i][j] = INT_MAX;}}
​pg->capacity *= 2;}// 插入顶点pg->vertices[pg->vSize++] = v;
}
​
void InsertArc(AMGraph* pg, VertexType v1, VertexType v2, ArcType cost)
{assert(pg);int pos1 = GetVertexPos(pg, v1);int pos2 = GetVertexPos(pg, v2);if (pos1 == -1 || pos2 == -1)return;
​if (pg->arcs[pos1][pos2] != INT_MAX)return;
​pg->arcs[pos1][pos2] = cost;++pg->aSize;
}
​
// 迪杰斯特拉算法的实现
void ShortestPath_DIJ(AMGraph* pg, VertexType v, int* D, int* Path)
{assert(pg);int pos = GetVertexPos(pg, v);if (pos == -1)return;
​bool* S = (bool*)malloc(sizeof(bool) * pg->vSize);assert(S);for (int i = 0; i < pg->vSize; ++i){S[i] = false;D[i] = pg->arcs[pos][i];if (i != pos && D[i] != INT_MAX)Path[i] = pos;elsePath[i] = -1;   }S[pos] = true;
​for (int i = 0; i < pg->vSize - 1; ++i){int min;int k;int flag = 1;for (int j = 0; j < pg->vSize; ++j){if (S[j] != false){continue;}if (flag){min = D[j];k = j;flag = 0;continue;}if (D[j] < min){min = D[j];k = j;}}
​S[k] = true;for (int j = 0; j < pg->vSize; ++j){
​if (S[j] == false && pg->arcs[k][j] != INT_MAX && D[k] + pg->arcs[k][j] < D[j]){D[j] = D[k] + pg->arcs[k][j];Path[j] = k;}}}
​free(S);
}

Test.c：

#include "AMGraph.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
​
int main()
{AMGraph g;AMGraphInit(&g);InsertVertex(&g, 'A');InsertVertex(&g, 'B');InsertVertex(&g, 'C');InsertVertex(&g, 'D');InsertVertex(&g, 'E');InsertVertex(&g, 'F');InsertArc(&g, 'A', 'C', 10);InsertArc(&g, 'A', 'E', 30);InsertArc(&g, 'A', 'F', 100);InsertArc(&g, 'B', 'C', 5);InsertArc(&g, 'C', 'D', 50);InsertArc(&g, 'D', 'F', 10);InsertArc(&g, 'E', 'D', 20);InsertArc(&g, 'E', 'F', 60);ShowAdjMatrix(&g);printf("\n");
​int* D = (int*)malloc(sizeof(int) * g.vSize);int* Path = (int*)malloc(sizeof(int) * g.vSize);assert(D && Path);ShortestPath_DIJ(&g, 'A', D, Path);
​for (int i = 1; i < g.vSize; ++i){if (D[i] == INT_MAX)printf("从 A 到 %c 没有路径！\n", g.vertices[i]);elseprintf("从 A 到 %c 的最短路径长度为：%d\n", g.vertices[i], D[i]);}free(D);free(Path);return 0;
}

---

三、弗洛伊德算法

求解每一对顶点之间的最短路径有两种方法：其一是分别以图中的每个顶点为源点共调用 n 次迪杰斯特拉算法；其二是采用下面介绍的弗洛伊德（Floyd）算法。两种算法的时间复杂度均为 O(n^3)，但后者形式上较简单。

弗洛伊德算法仍然使用带权的邻接矩阵 arcs 来表示有向网 G，求从顶点 vi 到 vj 的最短路径。

算法的实现要引入以下辅助的数据结构：

1. 二维数组 D[i][j]：记录顶点 vi 到 vj 之间的最短路径长度。

2. 二维数组 Path[i][j]：最短路径上顶点 vj 的前一顶点的序号。

算法步骤：

将 vi 到 vj 的最短路径长度初始化，即 D[i][j] = G.arcs[i][j]，然后进行 n 次比较和更新。

1. 在 vi 和 vj 间加入顶点 v0，比较 (vi, vj) 和 (vi, v0, vj) 的路径长度，取其中较短者为 vi 到 vj 的中间顶点序号不大于 0 的最短路径。

2. 在 vi 和 vj 间加入顶点 v1，得到 (vi, ..., v1) 和 (v1, ..., vj)，其中 (vi, ..., v1) 是 vi 到 v1 的且中间顶点序号不大于 0 的最短路径，(v1, ..., vj) 是 v1 到 vj 的且中间顶点的序号不大于 0 的最短路径，这两条路径已在上一步中求出。比较 (vi, ...., v1, ..., vj) 与上一步求出的 vi 到 vj 的中间顶点序号不大于 0 的最短路径，取其中较短者作为 vi 到 vj 的中间顶点序号不大于 1 的最短路径。

3. 依次类推，在 vi 和 vj 间加入顶点 vk，得到 (vi, ..., vk) 和 (vk, ..., vj)，它们分别是从 vi 到 vk 和从 vk 到 vj 的中间顶点序号不大于 k - 1 的最短路径，将 (vi, ..., vk, ..., vj) 和已经得到的从 vi 到 vj 且中间顶点序号不大于 k - 1 的最短路径相比较，其长度较短者便是从 vi 到 vj 的中间顶点的序号不大于 k 的最短路径。这样，经过 n 次比较后，最后求得的必是从 vi 到 vj 的最短路径。按此方法，可用同时求得各对顶点间的最短路径。

void ShortestPath_Floyd(AMGraph* pg, int** D, int** Path)
{assert(pg);for (int i = 0; i < pg->vSize; ++i){for (int j = 0; j < pg->vSize; ++j){D[i][j] = pg->arcs[i][j];if (i != j && D[i][j] != INT_MAX)Path[i][j] = i;elsePath[i][j] = -1;}}
​for (int k = 0; k < pg->vSize; ++k){for (int i = 0; i < pg->vSize; ++i){for (int j = 0; j < pg->vSize; ++j){if (i != k && j != k && i != j){if (D[i][k] != INT_MAX && D[k][j] != INT_MAX &&D[i][k] + D[k][j] < D[i][j]){D[i][j] = D[i][k] + D[k][j];Path[i][j] = Path[k][j];}}}}}
}

Test.c：

#include "AMGraph.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
​
int main()
{AMGraph g;AMGraphInit(&g);InsertVertex(&g, 'A');InsertVertex(&g, 'B');InsertVertex(&g, 'C');InsertVertex(&g, 'D');InsertArc(&g, 'A', 'B', 1);InsertArc(&g, 'A', 'D', 4);InsertArc(&g, 'B', 'C', 9);InsertArc(&g, 'B', 'D', 2);InsertArc(&g, 'C', 'A', 3);InsertArc(&g, 'C', 'B', 5);InsertArc(&g, 'C', 'D', 8);InsertArc(&g, 'D', 'C', 6);ShowAdjMatrix(&g);printf("\n");
​int** D = (int**)malloc(sizeof(int*) * g.vSize);assert(D);for (int i = 0; i < g.vSize; ++i){D[i] = (int*)malloc(sizeof(int) * g.vSize);assert(D[i]);}int** Path = (int**)malloc(sizeof(int*) * g.vSize);assert(Path);for (int i = 0; i < g.vSize; ++i){Path[i] = (int*)malloc(sizeof(int) * g.vSize);assert(Path[i]);}ShortestPath_Floyd(&g, D, Path);
​for (int i = 0; i < g.vSize; ++i){for (int j = 0; j < g.vSize; ++j){printf("%d ", D[i][j]);}printf("\n");}printf("\n");for (int i = 0; i < g.vSize; ++i){for (int j = 0; j < g.vSize; ++j){printf("%d ", Path[i][j]);}printf("\n");}
​free(D);free(Path);return 0;
}