14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的,这一次,让我们先人一步,趣学算法!欢迎记录下你的那些努力时刻(算法学习知识点/算法题解/遇到的算法bug/等等),在分享的同时加深对于算法的理解,同时吸收他人的奇思妙想,一起见证技术er的成长~
目录
迪杰斯特拉算法(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] == w;
的权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] + < dist[w] //说明我有一条更短的路径到w
dist[w] = dist[u] + //即更新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这条路径为起点,继续寻路。
后面的与这两步都一样,这里就不赘述啦,就留一点给小伙伴们发挥的空间,也可以将自己后续的寻路步骤发到评论区大家一起讨论哦。如果有帮助的话,欢迎点赞收藏哦~🤩,互通有无,互相进步。