前言

迪杰斯特拉(Dijkstra)算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中单源最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

不太懂的可以看视频 QWQ （来着@Abel）

Dijkstra算法讲解

算法实现：

  1. 定义一个数组dist[]，dist[i]表示从起点到顶点i的最短路径长度，初始化为无穷大，dist[s]=0，其中s为起点。
  2. 定义一个数组visited[]，visited[i]表示顶点i是否已经被标记为已确定最短路径的顶点，初始化为false。
  3. 从dist[]中找到当前未被标记的dist[i]最小的顶点u，标记visited[u]=true。
  4. 遍历所有与u相邻的顶点v，如果visited[v]=false，且从起点到u再到v的路径长度小于dist[v]，则更新dist[v]=dist[u]+w(u,v)，其中w(u,v)为边(u,v)的权值。

重复步骤3和步骤4，直到所有顶点都被标记为已确定最短路径的顶点。

以下是求无向网（储存方式为邻接矩阵）中起点s到各点的最短路径的代码：

#define _CRT_SECURE_NO_WARNINGS 1#include #include #include #define MVNum 100//最大顶点数#define MaxInt 66666//表示极大值typedef struct {char vexs[MVNum];//顶点表（顶点为字符型）int arcs[MVNum][MVNum];//邻接矩阵（权值为整型）int vexnum, arcnum;//图的当前点数和边数}AMGraph;//定位int LocateVex(AMGraph* G, char v) {int i;for (i = 0; i vexnum; i++) {if (G->vexs[i] == v) {return i;}}return -1;}//无向网的建立AMGraph* CreateUDN() {int i, j, k, w;char v1, v2;AMGraph* G = malloc(sizeof(AMGraph));printf("输入总顶点数，边数\n");scanf("%d%d", &G->vexnum, &G->arcnum);getchar();//吸收换行符printf("依次输入点的信息\n");for (i = 0; i vexnum; i++) {scanf("%c", &G->vexs[i]);}getchar();//吸收换行符for (i = 0; i vexnum; i++)for (j = 0; j vexnum; j++) {if (i == j) {G->arcs[i][j] = 0;}else {G->arcs[i][j] = MaxInt;}}for (k = 0; k arcnum; k++) {printf("输入一条边依附的顶点及权值\n");scanf("%c%c", &v1, &v2);scanf("%d", &w);getchar();//吸收换行符i = LocateVex(G, v1), j = LocateVex(G, v2);//确定v1、v2在顶点数组的下标G->arcs[i][j] = w;//边权值置为wG->arcs[j][i] = w;//无向网对称边权值也置为w}return G;}//输出邻接矩阵void print(AMGraph* G) {int i, j;printf("");for (i = 0; i vexnum; i++) {printf("%c ", G->vexs[i]);}printf("\n");for (i = 0; i vexnum; i++) {printf("%c ", G->vexs[i]);for (j = 0; j vexnum; j++) {if (G->arcs[i][j] == MaxInt)printf("∞ ");elseprintf("%d ", G->arcs[i][j]);}printf("\n");}}//迪杰斯特拉算法void Dijkstra(AMGraph* G, int s) {int dist[MVNum];//用来储存各顶点与起点的距离bool visited[MVNum];//用来标记已确定最短路径的顶点int i, j, k, u, min;//初始化数组dist与visitedfor (i = 0; i vexnum; i++) {dist[i] = MaxInt;visited[i] = false;}dist[s] = 0;//起始点s最短距离为0//每次循环会标记一个顶点u，直到所有顶点被标记（循环次数就是顶点数-1，起点已找到最短路径0）for (k = 1; k vexnum; k++) {min = MaxInt;//找到当前未被标记的距离起点最近的顶点ufor (i = 0; i vexnum; i++) {if (dist[i] arcs[u][j] arcs[u][j]小于顶点j距离起点s的距离dist[j]），更新顶点j距离起点的路径长度*/for (j = 0; j vexnum; j++) {if (!visited[j] && dist[u] + G->arcs[u][j] arcs[u][j];}}}//输出结果for (i = 0; i vexnum; i++) {printf("起点%c到顶点%c的最短路径为：%d\n", G->vexs[s], G->vexs[i], dist[i]);}}int main() {AMGraph* G = CreateUDN();printf("该无向网邻接矩阵为：\n");print(G);Dijkstra(G, 0);}

若顶点数为n，求解最短路径的主循环共进行n-1次，每次执行的时间为，所以算法时间复杂度为。

示例：

求如下图所示v0到各点的最短路径

运行结果如下：

A、B、C······代替v0、v1、v2······

总结

如果是有向网或者是以邻接表方式储存的有权图，算法实现流程还是一样的，只不过代码上大同小异。