最短路径问题（图表详解迪杰斯特拉算法）

首先，我们来看一下相关的图的一些基本知识点：

图：图 G=(V,E) 由顶点集 V 和边集 E 组成。每条边对应一个点对 (v,w)，其中 v，w 属于 V 。如果图中的点对是有序的，那么该图就是有向图，反之为无向图。

邻接点：若顶点 v 与 w 之间存在一条边，则认为顶点 v 与 w 邻接。

权：图中的每条边都可以对应一个数值，这种与边相关的数值称为权。

路径：在图 G 中，顶点 v1 到 vk 的路径是一个顶点序列 v1,v2,···,vk。

接下来我们进入正题：

单源最短路径问题，即在带权图中指定一个起始点 v ，找出从 v 到图中其余每个顶点的最短距离。迪杰斯特拉算法是解决单源最短路径问题的一个经典算法。该算法按阶段进行，在每个阶段，算法首先选择一个顶点 u ，该顶点在所有剩余顶点中与起始点 v 的距离最近，然后以此距离为基础，更新起始点 v 与其余未被选中的顶点之间的路径距离，接着继续进行选择，直到所有顶点都被选择到，算法结束。

具体步骤如下：

（1）假设 S 为已求得最短路径的终点的点集，在初始时，S只包含起始点v ，而点集 U 包含图中除了顶点 v 以外的所有顶点。

（2）从 U 中选择一个顶点 u ，它是源点 v 到 U 的距离最近的一个顶点，将 u 加入 S。

（3）继续从 U 中选择下一个与源点距离最近的顶点。

（4）重复步骤 3 ，直到点集 U 为空。

以上方无向有权图为例。具体实现过程中，我们需要创建三个辅助数组 Adjvex[]，Lowcost[]，Flag[]。Adjvex[i]=j 表示从起始点到达顶点 i 会经过顶点 j （主要用于求出最短路径）； Lowcost[i] 表示从起始点到顶点 i 的最短距离（初始化为无限大）； Flag[i] 标注顶点 i 是否已被选中（初始化为0）。用图表示程序实现过程如下：

1、这里我们以 v3 作为起始点。由于只有一个点，故Adjvex的值全为3；Lowcost 行加入各点到v3 的距离； Flag[3]置为1。如下图所示：

2、从剩下未选择的点中找出与源点距离最近的顶点，这里是v5，将 Flag[5] 置为1。由于加入了新点，我们要更新起始点 v3 与其余未被选中的顶点之间的路径距离，具体做法是：遍历v5 的所有邻接点，若v1到v5 的距离加上 v5 到某邻接点vk 的距离和小于原来v1 到vk的距离（ 即Lowcost[k] > Lowcost[5] + (v5,vk)的权值），则更新v1 到vk的距离，同时令Adjvex[k]=5。如下图所示：

3、与第2步相同，从剩下未选择的点中找出与源点距离最近的顶点，这里是v4，将 Flag[4] 置为1。然后，更新起始点 v3 与其余未被选中的顶点之间的路径距离，具体做法同上：遍历v4的所有邻接点，若v1到v4的距离加上 v4 到某邻接点vk 的距离和小于原来v1 到vk的距离（ 即 Lowcost[k] > Lowcost[4] + (v4,vk)的权值 ），则更新v1 到vk的距离，同时令Adjvex[k]=4。如下图所示：

4、继续重复上述步骤，直到所有顶点都被选择到，算法结束。最终表格如下：

程序代码：

# include <iostream># include <vector># define SIZE 20# define NEWSIZE 20# define Infinity 100000000 //表示无限大using namespace std;typedef struct ArcNode { //边的结点结构类型int adjvex; //该边的终点编号int weight; //该边的权值struct ArcNode* nextarc; //指向下一条边的指针}ArcNode;typedef struct VexNode { //顶点结构int num; //顶点编号ArcNode* firstarc; //指向第一条与该顶点有关的边的指针}VexNode;typedef struct Graph { //邻接表结构类型VexNode* VNode; //定义邻接表int vexnum, arcnum; //顶点数和边的个数int size; //邻接表的大小}Graph;int* Adjvex; //从起始点到达某顶点会经过的顶点int* Lowcost; //从起始点到某顶点的最短距离int* Flag; //标注顶点是否已被选中（初始化为0）void Create_Graph(Graph& G) //创建图的邻接表{cout << "顶点的个数:";cin >> G.vexnum;G.VNode = (VexNode*)malloc(SIZE * sizeof(VexNode));G.size = SIZE;while (G.size <= G.vexnum) { //根据点的个数动态分配空间G.VNode = (VexNode*)realloc(G.VNode, (G.size + NEWSIZE) * sizeof(VexNode));G.size += NEWSIZE;}Adjvex = (int*)malloc((G.size + 10) * sizeof(int));Lowcost = (int*)malloc((G.size + 10) * sizeof(int));Flag = (int*)malloc((G.size + 10) * sizeof(int));for (int i = 1; i <= G.vexnum; i++) {G.VNode[i].num = i;//给各点编号G.VNode[i].firstarc = NULL; //邻接表初始化，所有单向链表均为空表}cout << "请输入边的个数:";cin >> G.arcnum;cout << "请输入各边起点和终点的编号及权重：" << endl;int x, y, w; //x:起始点，y:终点，w:权重ArcNode* p, * q;for (int i = 1; i <= G.arcnum; i++) {cin >> x >> y >> w;p = (ArcNode*)malloc(sizeof(ArcNode)); //创建一个用于存放当前边的结点pp->nextarc = NULL;p->adjvex = y;p->weight = w;q = G.VNode[x].firstarc;//将边按顺序插入到链表末尾if (q == NULL) {G.VNode[x].firstarc = p;}else {while (q->nextarc != NULL) {q = q->nextarc;}q->nextarc = p;}p = (ArcNode*)malloc(sizeof(ArcNode));p->nextarc = NULL;p->adjvex = x;p->weight = w;q = G.VNode[y].firstarc;if (q == NULL) {G.VNode[y].firstarc = p;}else {while (q->nextarc != NULL) {q = q->nextarc;}q->nextarc = p;}}}void Dijkstra(Graph G, int v) //从顶点v出发求到其余顶点的最短路径{for (int i = 1; i <= G.vexnum; i++) { //初始化Adjvex[i] = v;Lowcost[i] = Infinity;Flag[i] = 0;}Lowcost[v] = 0;//初始点到初始点的距离为0Flag[v] = 1; //标注初始点int num = 1; //记录目前被选中的顶点数目ArcNode* p;while (num < G.vexnum) {p = G.VNode[v].firstarc; //p为新选中的点的第一个邻接点while (p != NULL) {//由于新点加入，更新起始点与其余未被选中的顶点之间的路径距离if (!Flag[p->adjvex] && Lowcost[p->adjvex] > Lowcost[v] + p->weight) {Lowcost[p->adjvex] = Lowcost[v] + p->weight;Adjvex[p->adjvex] = v;}p = p->nextarc;}int min = Infinity;for (int i = 1; i <= G.vexnum; i++) { //从未选择的顶点中找下一个与源点距离最近的顶点if (!Flag[i] && Lowcost[i] < min) {min = Lowcost[i];v = i;//更新v为目前与源点距离最近的顶点}}Flag[v] = 1; //标记新选中的点num++; //目前被选中的顶点数目+1}}int main(){Graph G;Create_Graph(G); //创建图int v;cout << "请输入起始点：";cin >> v;Dijkstra(G, v); //从顶点v出发求到其余顶点的最短路径for (int i = 1; i <= G.vexnum; i++) {if (i == v) {continue;}//输出起始点到各点的最短距离cout << "v" << v << " 到 " << "v" << i << " 的最短距离为" << Lowcost[i] << " ";//输出起始点到各点的最短路径cout << "路径为：" << "v" << v;int j = i;vector<int>Path;while (j != v) {Path.push_back(j);j = Adjvex[j];}for (int k = Path.size() - 1; k >= 0; k--) {cout << "->v" << Path[k];}cout << endl;}return 0;}

运行结果：

顶点的个数:5请输入边的个数:6请输入各边起点和终点的编号及权重：1 3 81 4 22 4 42 5 73 5 34 5 1请输入起始点：3v3 到 v1 的最短距离为6 路径为：v3->v5->v4->v1v3 到 v2 的最短距离为8 路径为：v3->v5->v4->v2v3 到 v4 的最短距离为4 路径为：v3->v5->v4v3 到 v5 的最短距离为3 路径为：v3->v5

总结：与普里姆算法（不知道的小伙伴可以看我之前的文章）类似，迪杰斯特拉算法的核心部分是一个双重循环。第一层循环是对所有的顶点；第二层有两个循环，一个是遍历邻接点更新数组 ，另一个是寻找 Lowcost 中的最小值。因此，迪杰斯特拉算法的时间复杂度为O(n^2)，n 表示图中顶点的个数。这里，我采用了邻接表的结构来实现程序，换成邻接矩阵，方法也是基本相同的，且无论采用哪种方式表示图，该算法的时间复杂度均为O(n^2)。

以上便是我个人的学习成果，很高兴能与大家分享。