【PAT】第十章 图算法专题
2021/7/17 1:05:31
本文主要是介绍【PAT】第十章 图算法专题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
第十章 图算法专题
10.4 最短路径
对于给定的图G
、起点S
和终点T
,求出S
到T
的最短路径
10.4.1 Dijkstra算法
单源最短路问题:给定图G
和起点S
,得到S
到其他每个顶点的最短距离。非负边。
集合S
存放已被访问过的顶点,执行n次以下步骤:
- 从集合
V-S
中选择与起点s距离最短的顶点u,访问u并加入集合S中。 - 另u为中介店,优化起点s到所有u能到达的顶点v(未被访问过的)之间的最短距离。
具体实现
- 集合S:bool vis[]
- 起点s到其他顶点的最短距离:int d[],初始化时,除d[s]=0外,其余初始化为inf
邻接矩阵实现
#include <cstdio> #include <algorithm> //fill头文件 using namespace std; //使用algorithm头文件的前提 const int MAXV=1000; //最大定点数 const int INF=1e9; int n,G[MAXV][MAXV]; int d[MAXV]; bool vis[MAXV]={false}; //初值为false,表示全都未被访问过 void Dijkstra(int s) { fill(d,d+MAXV,INF); d[s]=0; for(int i=0;i<n;i++) //循环n次 { int u=-1,MIN=INF; //MIN表示起点到V-S中顶点u的最小距离 for(int j=0;j<n;j++) { if(vis[j]==false&&d[j]<MIN) { u=j; MIN=d[j]; } } if(u==-1) return ; //剩下的顶点与s不通 vis[u]=true; //访问顶点u for(int v=0;i<n;v++) { //v未被访问过,u能到达v,d[v]能被优化 if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]) { d[v]=d[u]+G[u][v]; } } } }
复杂度:O(V2)
邻接链表实现
变种
无向边:指向相反的有向边
最短路径:前驱结点数组pre[],pre[v]表示从起点s到顶点v的最短路径上的v的前一个顶点。
for(int v=0;i<n;v++) { //v未被访问过,u能到达v,d[v]能被优化 if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]) { d[v]=d[u]+G[u][v]; pre[v]=u; //记录前驱结点 } } //输出最短路径 void dfs(int s,int v) { if(v==s) { printf("%d",s); return ; } dfs(s,pre[v]); printf("%d",v); }
最短路径不止一条:第二标尺
增加一个数组来存放新增的边权或点权或最短路径条数。
- 每条边再加一个权
增加一个数组c[]
if(vis[v]==false&&G[u][v]!=INF) { if(d[v]<d[u]+G[u][v]) { d[v]=d[u]+G[u][v]; c[v]=c[u]+C[u][v]; } else if(d[v]==d[u]+G[u][v]&&c[v]<c[u]+C[u][v]) //最短路径相同 { c[v]=c[u]+C[u][v]; //看第二标尺是否更优 } }
- 每个点增加一个权
if(vis[v]==false&&G[u][v]!=INF) { if(d[v]<d[u]+G[u][v]) { d[v]=d[u]+G[u][v]; w[v]=w[u]+weight[v]; } else if(d[v]==d[u]+G[u][v]&&w[v]<w[u]+weight[v]) //最短路径相同 { w[v]=w[u]+weight[v]; //看第二标尺是否更优 } }
- 问有多少条最短路径
if(vis[v]==false&&G[u][v]!=INF) { if(d[v]<d[u]+G[u][v]) { d[v]=d[u]+G[u][v]; num[v]=num[u]; } else if(d[v]==d[u]+G[u][v]) //最短路径相同 { num[v]+=num[u]; } }
这篇关于【PAT】第十章 图算法专题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22项目:远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
- 2024-12-21后台管理系统开发教程:新手入门全指南
- 2024-12-21后台开发教程:新手入门及实战指南
- 2024-12-21后台综合解决方案教程:新手入门指南
- 2024-12-21接口模块封装教程:新手必备指南
- 2024-12-21请求动作封装教程:新手必看指南
- 2024-12-21RBAC的权限教程:从入门到实践
- 2024-12-21登录鉴权实战:新手入门教程
- 2024-12-21动态权限实战入门指南