天津手机模板建站,内江规划建设教育培训中心网站,一个人做网站原型,中山市城市建设档案馆网站博主简介#xff1a;努力学习的大一在校计算机专业学生#xff0c;热爱学习和创作。目前在学习和分享#xff1a;算法、数据结构、Java等相关知识。博主主页#xff1a; 是瑶瑶子啦所属专栏: 算法 #xff1b;该专栏专注于蓝桥杯和ACM等算法竞赛#x1f525;近期目标努力学习的大一在校计算机专业学生热爱学习和创作。目前在学习和分享算法、数据结构、Java等相关知识。博主主页 是瑶瑶子啦所属专栏: 算法 该专栏专注于蓝桥杯和ACM等算法竞赛近期目标写好专栏的每一篇文章 目录一、简介二、基本思想策略三、代码实现输入格式输出格式数据范围3.1伪代码详解3.2源代码详解3.4数据结构优化3.3算法分析四、使用小根堆来优化Dijkstra算法五、深入和反思一、简介
Dijkstra算法适用于最短路问题中单源最短路只有一个起点并且每条边的权重都是正数的情况
二、基本思想策略
首先假定源点为u就是起点顶点集合V被划分为两部分集合 S 和 V-S。 初始时S中仅含有源点u其中S中的顶点到源点的最短路径已经确定。 集合S 和V-S中所包含的顶点到源点的最短路径的长度待定称从源点出发只经过S中的点到达V-S中的点的路径为特殊路径不一定是最短的 并用dist[]记录当前每个顶点对应的最短特殊路径长度。 红色顶点是S集合中均已经确定最短路径的点而绿色的是V-S集合中没有确定该顶点到源点最短路径的点。我们可以看到只经过S中的点到绿色点有两条特殊路径1520和2010但是只有一条最短路径1520那么绿色点就当前情况来看可以暂时把它的dist[i]更新为25但是一定是最短特殊路径吗不一定为什么呢我们接下来往下看 可以看到V-S集合中假设存在一点T经过这点到目的点的距离很有可能是目的点真正的dist 可能这里可能有点晕没错。上面只是一个大概的介绍我们接下来彻底揭开它的神秘面纱。 选择特殊路径长度最短的路径将其连接的V-S中的顶点加入到集合S中同时更新数组dist[]核心。一旦S包含了所有顶点dist[]就是从源到所有其他顶点的最短路径长度。
数据结构: h[N],e[M],ne[M],w[M]构建带权重的邻接表来存储图;int dist[N];//dist 数组保存源点到其余各个节点的距离
1初始化。令集合S{0}对于集合V-S中的所有顶点x{123…n}初始化dist数组memset(dist, 0x3f, sizeof(dist));//dist 数组的各个元素为无穷大,
2找最小。在集合V-S中依照贪心策略来寻找使得dist[j]具有最小值的顶点t,即dist[t]min则顶点t就是集合V-S中距离源点u最近的顶点。 3加入S战队。将顶点t加入集合S同时更新V-S 4借东风。在2中已近找到了源点到t的最短路径那么对集合V-S中所有与顶点t相邻的顶点j都可以借助t走捷径。 如果dist[i] min(dist[i], dist[t] w[j]);//更新 dist[j]转2。 光凭这个好像是这么回事但是细节值得推敲。这个题的本质还是贪心。 比如只看刚刚的文字不仔细分析你能不能解决我开头提出的那个问题 为什么这么说呢。因为在目前局部情况来看确实找到最短特殊路径了竟然就直接加入S战队不太可取就像我开头提出的在V-S集合中万一存在一个点经过这个点再到目的点很有可能才是真正的最短距离。 那为什么这个算法是可取的呢 巧就巧在最外层循环遍历了整个顶点并且并不是说一旦该顶点加入了S战队它的dist就不能变了相反它在实时更新。当循环遍历到绿色顶点T时会更新与它相连节点的dist。 不知道有没有get到我的意思虽然我没有用公式啥的去推导我个人也非常讨厌那种不人性化的方式更喜欢用一种形象的意会的方式去理解。 综上由局部最优到全局最优这种贪心的策略完全可以保证全部遍历和循环后dist[]数组中存的就是该点到源点的最短距离上面是我个人的理解欢迎一起讨论交流和学习捏
三、代码实现
这里是AcWing 849.Dijkstra求最短路 I模板题目
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离如果无法从 1 号点走到 n 号点则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
输出格式
输出一个整数表示 1 号点到 n 号点的最短距离。
如果路径不存在则输出 −1。
数据范围
1≤n≤500, 1≤m≤105, 图中涉及边长均不超过10000。
3.1伪代码详解
int dist[N],state[N];
dist[1] 0,state 1;//把源点加入S集合
for (i : 1~n)
{1),t-找最小找到只经过S中的点到V-S集合中某一点距离最小的那个V-S中的那个点2),state[t] 1;将t加入到S战队3),更新与t顶点相邻点的dist}3.2源代码详解
#includeiostream
#includecstring
#includealgorithmusing namespace std;//N是顶点数M是边数
const int N 510,M 100010;
int h[N],e[M],ne[M],w[M],idx;//邻接表存储图w[M]存储边的权重
int state[N];//state记录是否找到了源点到该节点的最短距离
int dist[N];//dist保存源点到其余各个顶点的最短特殊距离
int n,m;//图的顶点数和边数void add(int a,int b,int c)//插入边并给每个边赋值权重
{e[idx] b, w[idx] c, ne[idx] h[a],h[a] idx;
}
//key:核心和关键部分
void Dijkstra()
{memset(dist,0x3f,sizeof(dist));// 1)初始化dist数组dist[1] 0;//源点到源点的距离当然是0for (int i 0; i n; i)//对n个顶点进行n次遍历一开始V-S集合为n个元素,S集合是0个肯定是遍历n次才能完全遍历完{int t -1;//t存储当前这次遍历到的V-S集合中的点该点当前局部情况距离源点距离最小的那个点//2)在V-S中 找最小for (int j 1; j n; j){if(!state[j] (t -1 || dist[j] dist[t]))t j;}state[t] 1;//3)加入S 战队//3借东风for (int j h[t];j ! -1; j ne[j]){int i e[j];dist[i] min(dist[i],dist[t]w[j]);//更新dist[j]} }
}int main(){memset (h,-1,sizeof (h));//初始化邻接表cin n m;while (m--)//读入m条边{int a,b,w;cin a b w;add (a,b,w);}Dijkstra();if (dist[n] ! 0x3f3f3f3f)//如果dist[n]被更新了那么一定存在从1号节点到n号节点的最短距离路径cout dist[n];elsecout -1;
}关于存储图的适合没有考虑重边和自环的影响 因为在第三步更新的时候即使邻接表那条单链上有两个一样编号的节点但是第三步更新的时候还是会让对应编号节点的dist为最小。所以即使有重边也不影响 3.4数据结构优化
上面我们是采用邻接表来存储图邻接表的原理如下。邻接表是适合稀疏图当边比较多也就是稠密图时我们采用邻接矩阵来存储图。即g[a][b]的值为编号为a的节点a到编号为b的节点b之间的距离。 使用邻接矩阵注意去重边因为邻接矩阵只允许a→b的距离唯一。 #include cstring
#include iostream
#include algorithmusing namespace std;const int N 510;int n,m;int g[N][N];//邻接矩阵存储图
int dist[N];
bool st[N];int dijkstra(){memset(dist,0x3f,sizeof(dist)); dist[1] 0;for(int i 0; i n; i){int t -1;for (int j 1; j n; j )if (!st[j] (t -1|| dist[t] dist[j]))t j;st[t] true;for (int j 1; j n; j)dist[j] min(dist[j],dist[t] g[t][j]);}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];
}int main(){scanf(%d%d,n,m);memset(g,0x3f,sizeof g);//初始化邻接矩阵while(m--){int a,b,c;scanf(%d%d%d,a,b,c);g[a][b] min(g[a][b],c);//去除重边}int t dijkstra();printf(%d\n,t);return 0;
}3.3算法分析
算法时间复杂度时间复杂是 O(n2m)O(n2m), n 表示点数m表示边数
耗时的主要地方在于第2)步找最小每次都需要遍历一遍dist数组完全没有必要。可以使用小根堆来优化小根堆的数据结构可以自己来实现推荐或者用库中的
四、使用小根堆来优化Dijkstra算法 这个定义的heap完全可以看作集合V-S的具体化通过这个小根堆可以直接取出取出删除V-S集合的最小值。 #include cstring
#include iostream
#include algorithm
#include queue//堆的头文件using namespace std;typedef pairint, int PII;//堆里存储距离和节点编号const int N 1e6 10;int n, m;//节点数量和边数
int h[N], w[N], e[N], ne[N], idx;//邻接表存储图
int dist[N];//存储距离
bool st[N];//存储状态void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx ;
}int dijkstra()
{memset(dist, 0x3f, sizeof dist);//距离初始化为无穷大dist[1] 0;priority_queuePII, vectorPII, greaterPII heap;//小根堆heap.push({0, 1});//插入距离和节点编号while (heap.size()){auto t heap.top();//取距离源点最近的点heap.pop();int ver t.second, distance t.first;//ver:节点编号distance:源点距离ver 的距离if (st[ver]) continue;//如果距离已经确定则跳过该点st[ver] true;for (int i h[ver]; i ! -1; i ne[i])//更新ver所指向的节点距离{int j e[i];if (dist[j] dist[ver] w[i]){dist[j] dist[ver] w[i];heap.push({dist[j], j});//距离变小则入堆}}}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof h);while (m -- ){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}cout dijkstra() endl;return 0;
}
使用小根堆后找到 t 的耗时从 O(n^2) 将为了 O(1)。每次更新 dist 后需要向堆中插入更新的信息。所以更新dist的时间复杂度有 O(e) 变为了 O(elogn)。总时间复杂度有 O(n^2) 变为了 O(n elongn)。适用于稀疏图。
五、深入和反思
最开始我们说到Dijkstra算法只适用于边的权重都是正数的情况。为什么负权边不行呢
看一个Dijkstra算法失效的例子 A→B→D→E确定dist[E]20dist[D]8
然后A→C→D虽然更新了D点的dist使之正确dist[D]-1,但是由于D已经被遍历过无法通过D来更新E导致最终求出的A→E的最小距离出错。
为什么呢
D的dist的正确性不受负权的影响是因为负权指向的是D在更新节点更新dist的时候会更新掉D的错误值。但E就不一样了在当前局部只有D一个经过它D一旦遍历过后更新了E。当经过C到D时无法再通过正确的D去更新E
如果全部是正值的话在A→D时能一下子确定当前真正的dist[D]再dist[D]12那dist[E]也是正确的
所以根本原因在于存在负权边dist[D]的真值不能在更新dist[E]之前确定。
最后是我个人总结的理解
在Dijkstra算法视角把B遍历并进行相关更新后它当前得知了如下情况dist[A] 0,dist[B] 2,dist[D] 5,dist[C] 999,dist[D] 999C,C0,Dijkstra当然会放弃A-C-D这条路可是C其实0,这条路不该被放弃反而A-C-D的路径长度很有可能会小于A-B-C的长度正是由于Dijkstra的这点输入导致出现负权边时结果不正确再说人家的正确性本来就是建立在所有边的权重都0的基础上 Java岛冒险记【从小白到大佬之路】 LeetCode每日一题–进击大厂算法
