知识点

单源最短路径：Dijkstra

Dikstra算法也用来解决单源最短路径问题。Dijkstra是非常高效而且稳定的算法。

Bellman-Ford算法，提到它在现实中的模型是找警察问路。在现实中 Dijkstra有另外的模型，例如多米诺骨牌，可以想象下面的场景：

在图中所有的边上排满多米诺骨牌，相当于把骨牌看成图的边。一条边上的多米诺骨牌数量和边的权值(例如长度或费用)成正比，规定所有骨牌倒下的速度都是一样的。如果在一个结点上推倒骨牌，会导致这个结点上的所有骨牌都往后面倒下去。

在起点 s s s 推倒骨牌，可以观察到，从 s s s 开始。它连接的边上的骨牌都逐渐倒下，并到达所有能达到的结点。在某个结点 t t t ，可能先后从不同的线路倒骨牌过来；先倒过来的骨牌，其经过的路径肯定就是从 s s s 到达 t t t 的最短路径；后倒过来的骨牌，对确定结点 t t t 的最短路径没有贡献,不用管它。

从整体看,这就是一个从起点;扩散到整个图的过程。在这个过程中观察所有结点的最短路径是这样得到的:

1. 在 s s s 的所有直连邻居中，最近的邻居 u u u ，骨牌首先到达。 u u u 是第一个确定最短路径的结点。从 u u u 直连到 s s s 的路径肯定是最短的,因为如果 u u u 绕道别的结点到 s s s ，必然更远。
2. 然后，把后面骨牌的倒下分成两个部分，一部分是从 s s s 继续例下到 s s s 的其他的直连邻居，另一部分是从 u u u 出发倒下到 u u u 的直连邻居。那么下一个到达的结点 v v v 必然是 s s s 或者 u u u 的一个直连邻居。 v v v 是第二个确定最短路径的结点。
3. 继续以上步骤，在每一次迭代过程中都能确定一个结点的最短路径。

Dijkstra算法应用了贪心法的思想，即“抄近路走"，肯定能找到最短路径。

在上述步骤中可以发现：Dijkstra的每次选代，只需要检查上次已经确定最短路径的那些结点的邻居，检查范围很小，算法是高效的；每次迭代，都能得到至少一个结点的最短路径，算法是稳定的。

与Bellman Ford 对比:

Bellman-Ford 是分布式的思想;面 Dijkstra必须从起点s开始扩散和计算，是集中式的思想。读者可以试试在多米诺骨牌模型中运用Bellman-Ford,看看行不行。

算法实现

 
//算法7.15
void ShortestPath_DIJ(MGraph G, int v0, PathMatrix &P, ShortPathTable &D){ 
/* 	用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度 D[v]。若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。 final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径 算法7.15 */int v, w, i, j, min;Status final[MAX_VERTEX_NUM];for (v = 0; v < G.vexnum; ++v){final[v] = FALSE;D[v] = G.arcs[v0][v].adj;for (w = 0; w < G.vexnum; ++w)P[v][w] = FALSE; if (D[v] < INFINITY){P[v][v0] = TRUE;P[v][v] = TRUE;}}D[v0] = 0;final[v0] = TRUE;				// 初始化,v0顶点属于S集 for (i = 1; i < G.vexnum; ++i) 	//其余G.vexnum-1个顶点 { 								// 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 min = INFINITY; 						// 当前所知离v0顶点的最近距离 for (w = 0; w < G.vexnum; ++w)if (!final[w]) 						// w顶点在V-S中 if (D[w] < min){v = w;min = D[w];} 								//w顶点离v0顶点更近 final[v] = TRUE; 						// 离v0顶点最近的v加入S集 for (w = 0; w < G.vexnum; ++w) {		// 更新当前最短路径及距离 if (!final[w] && min < INFINITY&&G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w])){D[w] = min + G.arcs[v][w].adj;for (j = 0; j < G.vexnum; ++j)P[w][j] = P[v][j];P[w][w] = TRUE;}}}
}

完整代码

#include<bits/stdc++.h>
using namespace std;/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2 
typedef int Status; 
typedef int Boolean;  
#define MAX_NAME 5 
#define MAX_INFO 20 
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];/* ------------------  图的数组(邻接矩阵)存储表示    ----------------*/ 
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum { DG, DN, AG, AN }GraphKind; 
typedef struct{VRType adj; InfoType *info; 
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{VertexType vexs[MAX_VERTEX_NUM];AdjMatrix arcs; int vexnum, arcnum; GraphKind kind;
}MGraph;typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];/* -----------  需要用的图的数组(邻接矩阵)存储的基本操作 -----------*/int LocateVex(MGraph G, VertexType u){ 
/*  初始条件:图G存在,u和G中顶点有相同特征 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */int i;for (i = 0; i < G.vexnum; ++i)if (strcmp(u, G.vexs[i]) == 0)return i;return -1;
}Status CreateDN(MGraph &G){int i, j, k, w, IncInfo;char s[MAX_INFO], *info;VertexType va, vb;printf("请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0)(以空格作为间隔): ");scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);printf("请输入%d个顶点的值(<%d个字符):\n", G.vexnum, MAX_NAME);for (i = 0; i < G.vexnum; ++i) scanf("%s", G.vexs[i]);for (i = 0; i < G.vexnum; ++i) for (j = 0; j < G.vexnum; ++j){G.arcs[i][j].adj = INFINITY; G.arcs[i][j].info = NULL;}printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n", G.arcnum);for (k = 0; k < G.arcnum; ++k){scanf("%s%s%d%*c", va, vb, &w);  i = LocateVex(G, va);j = LocateVex(G, vb);G.arcs[i][j].adj = w;if (IncInfo){printf("请输入该弧的相关信息(<%d个字符): ", MAX_INFO);gets(s);w = strlen(s);if (w){info = (char*)malloc((w + 1) * sizeof(char));strcpy(info, s);G.arcs[i][j].info = info; }}}G.kind = DN;return OK;
}//算法7.15
void ShortestPath_DIJ(MGraph G, int v0, PathMatrix &P, ShortPathTable &D){ 
/* 	用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度 D[v]。若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。 final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径 算法7.15 */int v, w, i, j, min;Status final[MAX_VERTEX_NUM];for (v = 0; v < G.vexnum; ++v){final[v] = FALSE;D[v] = G.arcs[v0][v].adj;for (w = 0; w < G.vexnum; ++w)P[v][w] = FALSE; if (D[v] < INFINITY){P[v][v0] = TRUE;P[v][v] = TRUE;}}D[v0] = 0;final[v0] = TRUE;				// 初始化,v0顶点属于S集 for (i = 1; i < G.vexnum; ++i) 	//其余G.vexnum-1个顶点 { 								// 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 min = INFINITY; 						// 当前所知离v0顶点的最近距离 for (w = 0; w < G.vexnum; ++w)if (!final[w]) 						// w顶点在V-S中 if (D[w] < min){v = w;min = D[w];} 								//w顶点离v0顶点更近 final[v] = TRUE; 						// 离v0顶点最近的v加入S集 for (w = 0; w < G.vexnum; ++w) {		// 更新当前最短路径及距离 if (!final[w] && min < INFINITY&&G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w])){D[w] = min + G.arcs[v][w].adj;for (j = 0; j < G.vexnum; ++j)P[w][j] = P[v][j];P[w][w] = TRUE;}}}
}int main(){int i, j, v0 = 0; MGraph g;PathMatrix p;ShortPathTable d;CreateDN(g);ShortestPath_DIJ(g, v0, p, d);printf("最短路径数组 PathMatrix[i][j] 如下:\n");for (i = 0; i < g.vexnum; ++i){for (j = 0; j < g.vexnum; ++j)printf("%2d", p[i][j]);printf("\n");}printf("%s到各顶点的最短路径长度为：\n", g.vexs[0]);for (i = 1; i < g.vexnum; ++i)printf("%s-%s:%d\n", g.vexs[0], g.vexs[i], d[i]);return 0;
}

测试样例

请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0)(以空格作为间隔): 6 8 0
请输入6个顶点的值(<5个字符):
v0 v1 v2 v3 v4 v5
请输入8条弧的弧尾 弧头 权值(以空格作为间隔): 
v0 v5 100
v0 v4 30
v0 v2 10
v1 v2 5
v2 v3 50
v3 v5 10
v4 v3 20
v4 v5 60

运行结果

最短路径数组 PathMatrix[i][j] 如下:0 0 0 0 0 00 0 0 0 0 01 0 1 0 0 01 0 0 1 1 01 0 0 0 1 01 0 0 1 1 1
v0到各顶点的最短路径长度为：       
v0-v1:2147483647
v0-v2:10
v0-v3:50
v0-v4:30
v0-v5:60

更多数据结构代码实现请关注我的专栏数据结构

或者进入2021-10-16【严蔚敏数据结构代码实现合集】【c语言学习必备】学习

本文链接：https://my.lmcjl.com/post/9822.html