Loading... # **文中有自定义Makedown语法,建议在“[Zi_Gao的小站](https://www.zigao.info/892)”阅读!** # 图论之最短路径 ## 0000.什么是图 ### 00.图论简介 **图论 (Graph theory)** 是数学的一个分支,图是图论的主要研究对象。**图 (Graph)** 是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系。 示意图: ![p.webp][1] ### 01.图的概念 #### 00.组成部分 1. **顶点**:就是下**图中的圆圈**。上面的数字就是他的编号,用来描述不同的点。 2. **边**:下图中**连接两个圆圈的线**就是边。 3. **边权**:下图中边上面的数字就是边权。可以理解为**边的长度**,也就是两个点的距离。但实际上边**权是可以为负数**的,所以不是完全等于长度。 #### 01.相关概念 1. **无向图**:没有方向性的边组成的图。 2. **有向图**:有方向性的边组成的图。 3. **负权图**:**带有**负边权的图。 4. **正权图**:**没有**负边权的图。 5. **负环**:一个回路的**总权值**为负。 6. **重边**:一个点到另一个点有**多条边**。 7. **自环**:一个点有**自己到自己**的边。 8. **相邻**:两个点之间有**边**,则称之为相邻。 ## 0010.图的储存 ### 00.邻接矩阵 邻接矩阵的方法是用一个二维数组`e`,其中`e[i][j]`表示**i到j点的边权**。如果两个不相邻,则存为**正无穷**。 示意图: ![p2.webp][2] ![e.webp][3] ### 01.邻接表 邻接表是按边的方式进行的存储,我们需要把边进行编号从1->m。存储边的这一部分我们使用三个数组:`u` `v` `w`,其中`u[i]`表示**第i条边的起始点**,`v[i]`表示**第i条边的终止点**,`w[i]`表示**第i条边的边权**。然后我们还需要让边与顶点、边与边联系起来,我们使用`first[i]`表示**第i个点的第一条边**,`next[i]`表示第i条边的下一条边。 示意图: ``` 4 5 1 4 9 4 3 8 1 2 5 2 4 6 1 3 7 ``` ![邻接表_1.webp][4] eg遍历点1的边: ![邻接表.webp][5] ## 0011.图的遍历 ### 00.DFS #### 00.伪代码 ``` dfs(cur) cnt+1 if cnt=n stop for i:1->n if cur-j连接 and j未遍历 dfs(i) ``` ![dfs.webp][6] #### 01.模板代码 ```cpp /* *cur: 当前的点 *cnt:遍历的点个数 *INF:正无穷 *matrix:邻接矩阵 *book:标记数组 */ void depthFirstSearchMatrix(int cur){ printf("%d ",cur); ++cnt; if(cnt==n) return; for(int i=1;i<=n;i++) if(matrix[cur][i]<INF&&book[i]==0){ book[i]=1; depthFirstSearchMatrix(i); } return; } ``` ### 01.BFS #### 00.算法实现 使用一个队列que 1. 将源点s入队 2. 将对头p点**相邻**并且没有遍历的点入队,**将对头出队**。如果队列不为空,则执行2 ![bfs_1.webp][7] #### 01.伪代码 ``` que.push s while not que.empty cur=que.front for i:1->n if cur-i连接 i未遍历 que.push i que.pop ``` #### 10.模板代码 ```cpp /* *INF:正无穷 *cur: 当前的点 *matrix:邻接矩阵 *que:队列 *book:标记数组 */ void breadthFirstSearchMatrix(){ queue que; int cur=s; for(int i=0;i<MAX_N;i++)book[i]=0; que.push(cur); book[cur]=1; while(!que.empty()){ cur=que.front(); for(int i=1;i<=n;i++){ if(matrix[cur][i]!=INF&&!book[i]){ que.push(i); book[i]=1; } } printf("%d ",cur); que.pop(); } return; } ``` ## 0100.最短路径 ### 00.Floyd-Warshall Floyd-Warshall,是解决全源最短路径问题的算法,可以求出图上**任意两个点间**的最短路径。 #### 00.算法原理 要优化`S(i->j)`,**可以引入点k,使得`S(i->k)+S(k->j)<S(i->j)`** 示意图: ![3.webp][8] 那么我们枚举k,i,j则可以求出全源最短路径。 #### 10.伪代码 伪代码: ``` for k:1->n for i:1->n for j:1->n e[i][j]=min(e[i][k]+e[k][j],e[i][j]) ``` #### 11.模板代码 模板代码: ```cpp /* *k:中专点 *i:起始点 *j:终止点 *INF:正无穷 *matrix:邻接矩阵 */ void Floyd_WarshallMatrix(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) matrix[i][j]=min(matrix[i][k]+matrix[k][j],matrix[i][j]); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) if(matrix[i][j]==INF) printf("INF "); else printf("%d ",matrix[i][j]); putchar('\n'); } return; } ``` 明显看出,其时间复杂度为O(N^3) ### 01.Dijkstra Dijkstra/ˈdaɪkstrə/迪杰斯特拉算法是处理**一点到其余个点的短路**,也叫做"**单源最短路径**"。以下简称dij算法。实际上dij算法基于一个**没有负权**的图之上的一个**贪心**或者说**动归**算法。 #### 朴素版 ##### 00.算法原理 我们找到一个与源点s最相近的点k,标记k。并且遍历k的所有出边,如果p没有被标记**`S(s->k)+S(k->p)<S(s->p)`,则让`S(s->k)+S(k->p)=S(s->p)`** 枚举k,则可以求出以源点s的最短路径。 ##### 01.伪代码 伪代码: ``` init dis for i:1->n-1 min=find(dis) book u for j:1->n if !book j dis[j]=min(dis[u]+S(u->j),dis[j]) ``` ##### 10.模板代码 模板代码: ```cpp /* *matrix:邻接矩阵 *vis:记录是否访问过 *dis:记录距离 *min:记录最小距离 *u:记录最小距离的点 *INF:正无穷 */ void DijkstraMatrix(){ int dis[MAX_N]={0},_min,cur; book[s]=1; for(int i=0;i<MAX_N;i++)book[i]=0; for(int i=1;i<=n;i++) dis[i]=matrix[s][i]; for(int i=1;i<n;i++){ _min=INF; for(int j=1;j<=n;j++) if(!book[j]&&dis[j]<_min){ _min=dis[j]; cur=j; } book[cur]=1; for(int j=1;j<=n;j++) if(!book[j]) dis[j]=min(dis[cur]+matrix[cur][j],dis[j]); } for(int i=1;i<=n;++i) if(dis[i]==INF) printf("INF "); else printf("%d ",dis[i]); return; } ``` ##### 11.时间复杂度分析 从伪代码部分可以看出,dij算法主要有两部分组成: 1. 找到最短的出边O(N) 2. 松弛O(N) 所以时间复杂度总和为:**O(O(N)+O(N))*N=O(N^2)** #### 堆优化 ##### 00.算法原理 1. 找到最小出边这一部分使用**邻接表**优化到O(M),并且**使用堆寻找最小值优化到O(1)** 2. 松弛操作仍然需要**M**次,每次在堆上的修改需要**O(logN)** 所以时间复杂度总和为:**O(1)\*N+O(logN)*M=O(MlogN)** ##### 01.模板代码 ```cpp /* *h:可以直接在中间插入的堆 *list:邻接表 *dis:记录距离 *cur:当前的点 *to:去到的点 *INF:正无穷 */ void DijkstraHeapList(){ heap h; int dis[MAX_N],cur,to; for(int i=0;i<MAX_N;i++)dis[i]=INF; h.push((node){s,0}); dis[s]=0; while(!h.empty()){ cur=h.top().v; h.pop(); for(int i=head[cur];~i;i=list[i].next){ to=list[i].to; if((h.book[to]!=-1)&&(dis[to]>dis[cur]+list[i].w)){ dis[to]=dis[cur]+list[i].w; h.push((node){to,dis[to]}); } } } for(int i=1;i<=n;++i) if(dis[i]==INF) printf("INF "); else printf("%d ",dis[i]); return; } ``` ### 10.Bellman-Ford #### 00.算法原理 实际上可以知道最短路径中是没有环,这个时候分两种情况 1. 正环:如果有正环,那么去**掉这个环即可缩短**,所以不会有正环。 2. 负环:如果有负环,**一直走这个环即可一直缩短路程**,即不存在最短路,所有不会有负环。 根据这个结论还可知,最短路**最多经过n个点,n-1条边**,否则就有环了。这个结论介绍Bellman-Ford的基础,Bellman-Ford**可以判负环**也是更具这个结论。使用这个结论可以很简单写出Bellman-Ford算法: 1. 外层循环执行n-1次,注意**这里n-1次循环不代表遍历n-1个点**,这是有**n-1次松弛操作**。 2. 内层嵌套一个遍历m条边的循环。若第e条边可以使得:**`dis[v[e]]>w[e]+dis[u[e]]`**,则使**`dis[v[e]]=w[e]+dis[u[e]]`**完成松弛。 3. 两层循环完了之后,在进行一轮松弛,**若还可以松弛,则有负环**。 时间复杂度O(nm),实际上有时不需要跑完n-1次循环,**当本次循环没有松弛操作时**,即可停止。 ***注意!!!!***这里的判负环只是判断**源点出发联通的部分**是否有负环,真正的判负环应该创建一个超级源点,**与每个点都相邻,且边权为0**,然后以超级源点执行Bellman-Ford!!!! #### 01.伪代码 ``` init dis for i:0->n-1 flag=false for e:1->m if dis[e]<dis[u[e]]+w[e] flag=true dis[e]=dis[u[e]]+w[e] if !flag stop else if i=n-1 NO ANSWER ``` #### 10.模板代码 ```cpp /* *list:邻接表 *dis:记录距离 *flag:记录是否有松弛操作 *INF:正无穷 */ bool Bellman_FordList(){ int dis[MAX_N]; bool flag; for(int i=0;i<MAX_N;i++)dis[i]=INF; dis[s]=0; for(int i=0;i<n;i++){ flag=false; for(int e=1;e<=m;e++){ if(dis[list[e].to]>dis[list[e].from]+list[e].w){ flag=true; dis[list[e].to]=dis[list[e].from]+list[e].w; } } if(!flag) break; else if(i==n-1){ printf("No answer!"); return false; } } for(int i=1;i<=n;++i) if(dis[i]==INF) printf("INF "); else printf("%d ",dis[i]); return true; } ``` ### 11.SPFA #### 00.算法原理 实际上在Bellman-Ford算法中,很多的松弛操作是并不需要的。只有一个点被其他点松弛过,这个点才有可能继续,维护一个队列中有可以引起松弛的点。那么SPFA也可以判负环,只要一个点入队了n次是,即发生了n次松弛,即最短路经过了n条边,所以会有负环。具体来说: 1. 将源点s入队,执行2。 2. 取出对头u,将u相邻的点遍历v,若**`dis[v]<dis[u]+S(u->v)`**,则**`dis[v]=dis[u]+S(u->v)`**,并计入v的入队次数。 #### 01.伪代码 ``` init dis,cnt,book que.push s while not q.empty u=q.front q.pop for q->v if dis[u]<dis[v]+S(u->v) dis[u]=dis[v]+S(u->v) if not book v cnt[v]+1 if cnt[v]==n NO ANSWER q.push v book v ``` #### 10.模板代码 ```cpp /* *list:邻接表 *q:队列 *dis:记录距离 *book:是否在队列中 *cnt:记录入队此时 *cur: 当前的点 *to:去到的点 *INF:正无穷 */ bool SPFAList(){ queue q; int dis[MAX_N],cnt[MAX_N]={0},cur,to; memset(book,0,sizeof(book)); for(int i=0;i<MAX_N;i++)dis[i]=INF; q.push(s); dis[s]=0; book[s]=1; cnt[s]=1; while(!q.empty()){ cur=q.front(); q.pop(); book[cur]=0; for(int i=head[cur];~i;i=list[i].next){ to=list[i].to; if(dis[to]>dis[cur]+list[i].w){ dis[to]=dis[cur]+list[i].w; if(!book[to]){ cnt[to]++; if(cnt[to]>=n){ printf("No answer!"); return false; } q.push(to); book[to]=1; } } } } for(int i=1;i<=n;++i) if(dis[i]==INF) printf("INF "); else printf("%d ",dis[i]); return true; } ``` 实际上SPFA**最坏时间复杂度仍然是O(nm)**,但在随机图中表现极为优异。于是就有了卡SPFA的说法 #### 10.卡SPFA ![spfa.webp][9] [1]: https://www.zigao.info/assets/article/2022/08/200323797.webp [2]: https://www.zigao.info/assets/article/2022/08/1432291327.webp [3]: https://www.zigao.info/assets/article/2022/08/3471413186.webp [4]: https://www.zigao.info/assets/article/2022/08/1281377881.webp [5]: https://www.zigao.info/assets/article/2022/08/748359408.webp [6]: https://www.zigao.info/assets/article/2022/08/812818287.webp [7]: https://www.zigao.info/assets/article/2022/08/1571152207.webp [8]: https://www.zigao.info/assets/article/2022/08/2439217289.webp [9]: https://www.zigao.info/assets/article/2022/08/872702653.webp 最后修改:2023 年 11 月 10 日 © 允许规范转载 打赏 赞赏作者 赞 2 如果觉得我的文章对你有用,请随意赞赏
1 条评论
我喜欢MuC,大佬能教我怎么追吗?