算法学习-图论-图的存储-最短路
题目概述及细节
单源最短路，模板，luoguP3371
单源最短路，模板
dij算法
核心是把节点分为两类，一类是以确定到起点最短的距离，一类是没有确定
- 初始时所有都未确定
- 从没有确定的节点中选取一个距离起点最短的
- 依据此点确定别的未更新的点的距离
首先补充题目中常见的数值：
int -2^31=-21 4748 3648 到 2^31-1=21 4748 3647。共10位数字,最大整数用十六进制表示07fffffff(共32位，4位为一组)
memset是对字节进行赋值，例如：
int a[10]; memset(a,0x3f, sizeof(a));//实际上a数组中每个元素均为0x3f3f3f3f,sizeof返回a所占的字节数40，也就是每个字节均被赋值为0x3f,最终又以四个字节合为int ps:声明的全局变量默认初始化为0，在函数内则不为
由于0的表示为0x00,-1在计算机内用补码表示为0xff,所以两个在进行memset操作后所得结果仍为原来的，而1就不能。
而题目中说明所有w之和 < 2^31,也就是说明dis数组可以为int数组。
对于此题数据1 <= n <= 104来讲，用邻接矩阵存储需要大约100mb，可能可以，但还没尝试。(**也不行qwq**,对于大多数题目，若n>104,申请二维数组的时候就需要注意了)对另一道题1 <= n <= 10^5来说，就完全不能用邻接矩阵来存储了，故采取用链式前向星模拟邻接表的方式来存储边。
不论是用邻接矩阵还是模拟邻接表的方式，单源最短路径的要素有
- visit[]：标记是否已经取得最优解
- dis[]:存储起点到该点的权值
邻接矩阵解法
邻接矩阵dij
//变量声明 const int MaxN = 1002;//适题目而定 int dis[MaxN]; int visit[MaxN]; int e[MaxN][MaxN];//存储边的关系, 此处读入需要注意有向图和无向图的区别,起始需要初始化相应值 int n, m, s;//点数，边数，起点 void dij(){ //变量初始化 memset(dis, 0x3f, sizeof(dis)); memset(visit, 0, sizeof(visit)); dis[s] = 0;//使起点第一个被拿出来用来更新别的边 for(int k = 0; k < n;k++){//每次确定一个点，n次循环结果必然确定 int u;//记录当前离起点最近的点 int minNum = INT_MAX;//需要包含头文件<climits>，整数的最大值 for(int i = 1; i <= n; i++){//在没有确定的点中选一个离起点最近的 if(!visit[i] && minNum > dis[i]){ minNum = dis[i]; u = i; } visit[u] = 1;//u距离起点的最短距离确定了 for(int i = 1; i <= n; i++){//遍历u的所有未确定最短距离的邻接点，若经过u点比不经过u点所得到的最短距离变小，则更新 if(visit[i]){ continue; } if(dis[i] > dis[u] + e[u][i]){ dis[i] = dis[u] + e[u][i]; } } } } } 可以看到用邻接矩阵主要利用了其来遍历选出来的u的所有邻接点，还有u->i的权重。所以我们所选的数据结构只需要能够实现这两个要求就可以实现算法。
- 可以遍历u的所有邻接点
- 可以知道所有边的权重
在上面算法中可以优化的是选u的过程。可以利用stl中的优先级队列来选择当前距离起点最短的点。只需要在每次更新的时候把更新节点入队（此时我们需要的有当前最短的是哪个节点还有其到起点的距离，所以我们需要一个node结构体(包含位置，还有距离,也就是存点)或者stl提供的pair作为队中的元素。
priority_queue
结构体
堆优化邻接矩阵dij
//结构体 struct node{ int pos; int dis; bool operator<(const node &x) const{//重载<运算符，自定义优先级,const 必须加 return dis > x.dis; } } priority_queue<int, int> pq; void dij(){ memset(dis, 0x3f, sizeof(dis)); memset(visit, 0, sizeof(visit)); q.push_back(node{s, 0}); while(!q.empty()){//此处还可以定义一个cnt变量来表示循环了几次，因为每次循环确定一个点距离起点最近的距离，最后若cnt < n, 表示图并不联通 node temp = q.top();//其实是堆，不是front q.pop(); int u = temp.pos; int d = temp.dis;//此时就相当于上方的循环求最小的结果,由于上方还有个限制，就是在没有访问过的节点中选取距离起点最短的点，所以需要判断如果u已经确定，继续下次循环 if(visit[u]){ continue; } visit[u] = 1; for(int i = 1; i <= n; i++){ if(visit[i]){ continue; } if(dis[i] > dis[u] + e[u][i]){ dis[i] = dis[u] + e[u][i]; pq.push(i, dis[i]); } } } } 输出起点到某节点的最短路径
需要记录一个记录节点前驱的数组pre,初始化每个节点的前驱都是自己（这也是最后回溯的时候停止的条件）
而更新pre的时候显然就是确定最短节点后更新其他点离起点距离成功的时候pre[i] = u
//输出路径,利用vector来记录路径 vector<int> res; void getPath(int d){ if(pre[d] == d){ return; } getPath(pre[d]); res.push_back(pre[d]);//最后需要把终点入res } 多优先级的解法
在稍微复杂一些的题目中，题目除了要求距离起点最短的条件下，若相同则选择**（价格，经过节点更多）更大的路径，这也只是需要在判断能否更新节点时再添加一个else if分支在距离相等情况下判断这点离起点的别的条件的大小然后判断是否更新。
链式前向星解法
链式前向星存图
一个图由点还有边组成，大部分边具有权值。故把这三部分存储下来就掌握了一个图，并且要具备从一个已知顶点遍历与它相邻顶点的作用。而对于普通的邻接矩阵来说，对其中一行遍历的过程中就是遍历与之相邻的顶点的过程。元素值即为权重。在稀疏图中显然过于浪费。
而链式前向星我们用结构体egde来表示边，用辅助数组head表示以i为起点的最后一条边的存储下标,一些全局的cnt下标辅助添加边
const int MAXN=1002; int head[i], int cnt = 1;//初始化为-1 struct edge{ int next;//与u同起点的上一条边的下标 int to;//第i条边的终点 int w; }e[MAXN]; void addEdge(int u, int v, int w){ e[cnt].to = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt++; } 普通dij
void dij(){
memset(dis, 0x3f, sizeof(dis));
memset(visit, 0, sizeof(visit));
dis[s] = 0;
for(int k = 0; k < n; k++){
int u, minNum = INT_MAX;
for(int i = 1; i < n; i++){
if(!visit[i] && minNum > dis[i]){
u = i;
minNum = dis[i];
}
}
visit[u] = 1;
for(int i = head[u]; i != -1; i = e[i].next){//遍历每个与u相连的每条边
int y = e[i].to;
if(visit[y]){
continue;
}
if(dis[y] > dis[u] + e[i].w){
dis[y] = dis[u] + e[i].w;
}
}
}
}
堆优化的dij
//node节点和priority_queue与上方一致 void dij(){ memset(dis, 0x3f, sizeof(dis)); memset(visit, 0, sizeof(visit)); dis[s] = 0; pq.push(node{s, 0}); while(!pq.empty()){ node temp = pq.top(); pq.pop(); int u = temp.pos; //int d = temp.dis; if(visit[u]){ continue; } visit[u] = 1; for(int i = head[u]; i != -1; i = e[i].next()){ int y = e[i].to; if(dis[y] > dis[u] + e[i].w){ dis[y] = dis[u] + e[i].w; pq.push(node{y,dis[u]}); } } } } vector模拟邻接表求解
主要利用vector数组来存储每条边所连接的节点和此边的权重，所以需要自定义一个node2类型的结构体表示终点和权重，以方便后边查询。
struct node2{ int to; int w; }; vector<node> v[MAXN]; void dij(){ memset(dis, 0x3f, sizeof(dis)); pq.push(node2{s, 0}); dis[s] = 0; while(!pq.empty()){ node2 temp = pq.top(); pq.pop(); int u = temp.pos; if(visit[u]){ continue; } visit[u] = 1; for(int i = 0;i < v[u].size();i++){ int y = v[u][i].to; if(visit[y]){ continue; } if(dis[y] > dis[u] + v[u][i].w){ dis[y] = dis[u] + v[u][i].w; pq.push(node2{y, dis[y]}); } } } } 每日小代码复习整理
快速幂求mod
luogup1226
观察题目只有a在计算过程中可能会爆int
typedef long long ll; int fp(ll a, int p, int m){//部分题目得开long long, int res = 1; while(p){ if(p & 1){ res = res * a % m; } a = a * a % m; p /= 2; } return res; } 求解斐波那契数列
辗转相除法
int gcd(int a, int b){ return b == 0 : a ? gcd(b, a % b); } 参考博客
链式前向星理解
priority_queue用法
快速幂理解
小感悟
自从学习算法以来，自己遇到了很多的挫折，基本每次都是去当分母去的。但慢慢的我明白了，大家的起点有快有满，大学之前我连C语言是什么都不知道，大一的C语言也是70多，之后了解到了算法竞赛，连校内的选拔赛都够呛。就这样，对算法学习的恐惧埋下了种子。步入大二，我依旧想要提升自己的编程能力，但是也是进步缓慢。直到现在，我慢慢的感受到了学习算法一方面是为了以后的就业，一方面会真的让自己享受到调试代码，锻炼思维的乐趣。我也并不注重别人有多么强，我现在只想学习到切切实实的知识以及算法当中的精妙之处。当我发现我深搜填了一行代码就可以让其原路返回的节点也记录下来，从而解决了自己问题时，我才真正的被其中折服。在自己慢慢的看到题目有所思路，我真心感到开心。之后我也会继续前行，丰富自己的知识。
另外，我也慢慢的知道了和自己未来的生活，工作相比，现阶段的失败，不开心，其实都没有值得难过的，它们只是为自己的前进指明了方向。而面对生活，有自己的目标，有自己的兴趣，喜欢作的事情，有自己独立的思考这莫大重要。
世界之大，比自己强的比比皆是。但我仍然会自信的面对学习，生活，因为我需要让自己成为自己心中的模样。（做着自己喜欢作的事情，热爱生活，健康学习，让家人幸福）