目录
迪杰斯特拉算法介绍
算法知识点
算法思路
算法前的准备
算法步骤
模板代码
例题带图解析
正文
迪杰斯特拉算法介绍
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
迪杰斯特拉算法用于查找图中某个顶点到其它所有顶点的最短路径，该算法既适用于无向加权图，也适用于有向加权图。
注意，使用迪杰斯特拉算法查找最短路径时，必须保证图中所有边的权值为非负数，否则查找过程很容易出错。
算法知识点
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯
算法思路
通过Dijkstra计算图G中的最短路径时，需要指定一个起点D(即从顶点D开始计算)。
此外，引进两个数组S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点D的距离)。
初始时，数组S中只有起点D；数组U中是除起点D之外的顶点，并且数组U中记录各顶点到起点D的距离。如果顶点与起点D不相邻，距离为无穷大。
然后，从数组U中找出路径最短的顶点K，并将其加入到数组S中；同时，从数组U中移除顶点K。接着，更新数组U中的各顶点到起点D的距离。
重复第4步操作，直到遍历完所有顶点。
算法前的准备
需要借助三个辅助向量（数组）：
v：表示以v为下标的起点
1.数组 s[n] 标记这个最短路径有没有被求出
s[i] = 1; 当源点v到vi的最短路径求出
s[i] = 0; 源点v到vi的最短路径没有被求出
s[0]: 表示v->v0的最短路径有没有被求出
s[1]: 表示v->v1的最短路径有没有被求出
s[2]: 表示v->v2的最短路径有没有被求出
....
s[i]: 表示v->vi的最短路径有没有被求出
初始时，s[v] = 1,其它的s[i] = 0
2.数组dist[n] 最短路径距离
dist[i] 源点v到vi的最短路径长度
初始时：
dist[i] = <v,vi> = w;
<v,vi>的权w，若p(v,vi)存在，表示v到vi有一条直接路径
dist[i] = VERY_BIG ,p(v,vi)不存在，表示v到vi没有一条直接路径
3.path[n]
源点v到vi的最短路径 (v,...vi)
初始时，path[i] = {v}
算法步骤
假设图中有n个顶点，Dijkstra是要求n-1条最短路径，即源点v到其它n-1个顶点的边（最短路径）
step1:
源点v到其它各个顶点的第一条最短路径长度 dis[u] = MIN{dist[w]| w= 0,1,2..n-1且s[w] = 0}
表示：
在所有没有被找到最短路径中找到一条最短的，这条路径当做当前求出的最短路径长度。
eq: dist[B] = Min{dis[B], dist[C],dist[D]}
假设dist[B]为最短路径
即A-B （源点A）的最短路径为dist[B] 且 s[B] = 1;
证明：
A->B
用穷举法：
A->B : dist[B]
A->C->B :dist[c] + x > dist[B]
所以得证。
dist[u]最为当前最短路径 s[u] = 1：表示v->u的最短路径已经被求出。
step2:
对所有s[w] = 0(其它所有未被求出的最短路径的点)，更新dist[w]
if dist[u] + <u , w> < dist[w] //说明我有一条更短的路径到w
dist[w] = dist[u] + <u , w> //即更新dist[w]
把step1 step2 重复n-1次 就可以求出最短距离
模板代码
int s[MAXN];//是否已经求出最短路径的标志数组 s[i]==1 :表示v到vi最短路径已经求出 ； s[i] == 0:表示v到vi最短路径没有求出 int dist[MAXN];//存放当前源点到各顶点的最短路径长度 int path[MAXN];//存放的源点到终点i的最短路径是利用哪个最优点更新的 //用迪杰斯特拉算法求出v点到其它各顶点的最短路径 void Dijkstra(Graph *g, int v) { //step 1 初始化辅助数组 int i; for( i = 0; i < g->vexnum; i++) { s[i] = 0;//一开始都为0 dist[i] = g->Adj[v][i];//邻接矩阵权值 path[i] = v;//每条最短路径起点都为v } s[v] = 1; dist[v] = 0; //step2 在所有没有被求出来的最短路径找出一条最短的 长度当成当前求出的最短路径 int min;//求最优顶点的记录板 int i_min;//最优顶点下标 int times; //寻找最短路径的次数 每次只找一条n-1 for(times = 0; times < g->vexnum-1; times++) { //step1 求出当前最优顶点 min = VERY_BIG; for(i = 0; i < g->vexnum; i++) { if(s[i] == 0 && dist[i] < min) { min = dist[i]; i_min = i; } } s[i_min] = 1;//最短路径已经求出 //step2 根据最优顶点更新其它dist for(i = 0; i < g->vexnum; i++) { if(s[i] == 0) { if(dist[i_min] + g->Adj[i_min][i] < dist[i]) { dist[i] = dist[i_min] + g->Adj[i_min][i]; path[i] = i_min; } } } } } // a -> b: 15 输出所有最短路径值 void print_dist(Graph *g, int v) { int i; for(i = 0; i < g->vexnum; i++) { printf("the %c -> %c : %d\n",g->V[v], g->V[i], dist[i]); } } void print_path(Graph *g, int v) { int i; for(i = 0; i < g->vexnum; i++) { if(dist[i] == VERY_BIG) { printf("%c -> %c is no path\n",g->V[v], g->V[i]); continue; } } printf("%c ->%c : %c",g->V[v], g->V[i],g->V[i]); int pre_index = path[i]; while(1) { printf("%c ",g->V[pre_index]); if(pre_index == v)//已经回到了出发点 { break; } pre_index = path[pre_index]; } printf("\n"); }
例题带图解析
例题来源，自创，是笔者经过计算后，包含了大部分情况。 （求A点到各点的最短路径）
名称解释：
标志：为1 时表示已找到最短路径，为0 时表示还未找到最短路径
距离：目前从A点到目的点的最短距离
路径：目前从A点到目的点的最短路径
--：目前无法到达
这是第一轮寻路，以A为起点。
A |
B | C | D | E | F | G | |
| 标志 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 距离 | 0 | 3 | 2 | -- | -- | -- | -- |
| 路径 | A | A->B | A->c | -- | -- | -- | -- |
上述距离最短的是A->C为2，因此C的最短路径找到了,C的标志为变为1，下一轮以A->C这条路径为起点，继续寻路
第二轮寻路，以A->C为起点，图中可以看出，C继续往下走，可以到D点与F点。
A |
B | C | D | E | F | G | |
| 标志 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 距离 | 0 | 3 | 2 | 10 | -- | 6 | -- |
| 路径 | A | A->B | A->C | A->C->D | -- | A->C->D | -- |
比较距离时，比较的是标志位为0的有数距离，第二轮就算比较B，D，F三点距离，这里可以看到A->B距离最小，因此到B点的最小路径找到，为A->C，距离为2。下一轮以A->C这条路径为起点，继续寻路。
后面的与这两步都一样，这里就不赘述啦，就留一点给小伙伴们发挥的空间，也可以将自己后续的寻路步骤发到评论区大家一起讨论哦。互通有无，互相进步。
