关于图论
对于本篇而言，笔者就对考点中的最短路径问题进行总结和分享，其他图论问题后续持续更出呀~
知识铺垫
图的定义
一般用一个二元组G = (V , E) 或 G = < V , E >来定义和描述一个图。其中V是图G的顶点集合，E是图G中边的集合。
圆括号"()"用于表示无向图
尖角括号"<>"用于表示有向图
对于一张有向图，我们一般使用邻接矩阵和邻接表这两种存储方式。对于无向图，可以把无向图看做两条方向相反的有向边，因此无向图可以看做特殊的有向图，所以我们在后续的例题中，就只对有向图进行探讨啦
邻接矩阵
说通俗简单一点，就是将题目中所给的信息，映射到一个二维矩阵中。
结合上图而言，0号点可以走到1号点，就在右侧的二维矩阵中，对应(0,1)的位置标记上1,0号点不能走到2号点，就让(0,2)这个点仍旧是0,0号点可以走到3号点，就让(0,3)标记上1，其他点以此类推
邻接表
说简单粗暴一点，就是根据题目所给的信息，将一些连通的点，串到一个链表上
依旧用刚才的村落举例子，4号点可以走到2号、5号、9号点，就把它们串在一个链表上。整个的0~9号点并排写出来
最短路算法总大纲
友友们，这张图中，不同背景下如何使用相应类型的最短路算法以及各个最短路算法的时间复杂度是要铭记于心的喔
dijkstra算法
朴素版dijsktra算法（适用于稠密图）
例题描述
传送门
题目中阐述了不存在负权边，再根据题目所给的数据范围来看，点的数量很少，边很多，因此可以发现是稠密图，那么可直接用朴素版的dijkstra求解了。
参考代码(C++版本)
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int N = 510; int n,m; //图中的点和边 int g[N][N]; //邻接矩阵 int dist[N]; //表示从1号点到图中每个点的距离 bool st[N]; //存放已经确定最短路的点 //补全调用的函数 void dijkstra() { memset(dist,0x3f,sizeof dist); //处理距离数组dist,先把所有点都置为正无穷 dist[1] = 0; //处理1号点，表示1号点到1号点的距离是0 //n-1次循环 for(int i = 0; i < n-1;i++) { int t = -1; //处理每个点 for(int j = 1; j <= n;j++) //如果当前j没有在st这个记录状态的数组中 //t == -1 || dist[t] > dist[j] 意思是这个t之前被其他的j赋值了，现在有个更好的出现了，或者要么这个t的值直接就没有被修改过 if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true; //把这个点假如到集合中 //用t去更新其他点到1号点的距离 for(int j = 1; j <= n;j++) dist[j] = min(dist[j],dist[t]+g[t][j]); } } int main() { //输入点和边 scanf("%d%d",&n,&m); //初始化邻接矩阵 memset(g,0x3f,sizeof g); //m次询问，进行建图的过程 while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); //存到图中，只是要处理一下重边 g[a][b] = min(g[a][b],c); } //调用dijkstra dijkstra(); //输出结果 if(dist[n] == 0x3f3f3f3f) printf("%d",-1); else printf("%d\n",dist[n]); return 0; }
算法模板
朴素版dijkstra算法的具体操作流程可以用下图描述：
朴素版dijkstra算法的具体代码模板如下：
int g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路是否已经确定 void dijkstra() { //初始化环节 memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n - 1; 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; // 用全局最小变量t去更新其他点的距离 for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], dist[t] + g[t][j]); } }
细节落实
一、重边
在建图的时候，需要着重处理重边，最后只留下最短的那条边来构建图
while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); /使用min函数筛选出最短的那条边来建图 g[a][b] = min(g[a][b],c); }
二、初始化环节的思想
使用memset函数，对所给地址按照字节初始化。 因为是求最小的路径，所以先将1号点到每个点的距离初始化为一个很大的数据，同时将1号点到1号点的距离是0敲定
memset(dist,0x3f,sizeof dist); dist[1] = 0;
三、在还未确定最短路的点中，寻找距离最小的点
整段代码的核心是"!st[j]",一切操作都是在当前准备探索的这个点j在没有被确定的情况下进行的。
对于： int t = -1; 其意思是声明了一个变量t，用于记录对于全局而言的最小值，最开始的时候赋值为一个不存在的-1。 用这个最小值去更新它的所有出边，同样也是按照寻找全局最小值的思想进行下去，那么最后就可以获得最短路径
最后在n个点都尝试完了以后，将这个全局最小变量t放到记录已经确定最短路状态的数组st中“st[t] = true”
for (int i = 0; i < n - 1; 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;
堆优化版dijkstra算法（ 适用于稀疏图）
由上面的程序代码可以看出来它的时间复杂度是O(n2),影响效率的主要瓶颈是在寻找全局最小变量这里，它挨着挨着去枚举了，效率就会比较差啦
因此可以用一个堆对dist数组进行维护，用O(logn)的时间获取最小值并从将它从堆中删除，再用O(logn)的时间执行一条边的拓展和更新，最终可用O(mlogn)实现堆优化版本的dijkstra算法。
例题描述
传送门
参考实现代码(C++版本)
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; typedef pair<int,int> PII; //使用一个pair数对维护距离和结点的编号 int n,m; const int N = 1e6+10; int h[N],e[N],ne[N],w[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++; } void dijkstra() { //初始化环节 memset(dist,0x3f,sizeof dist); dist[1] = 0; //使用STL容器建立一个小根堆 priority_queue<PII,vector<PII>,greater<PII>> heap; heap.push({0,1}); //数对的first属性是距离，second属性是结点 //当堆不空时，进行操作 while(heap.size()) { //每次取出当前距离最小的点，对于小根堆，也就是堆顶 auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if(st[ver]) continue; //如果这个结点已经在st中了，说明当前探索的是冗余备份，跳过就好 st[ver] =true; //标记这个结点已经是确定最短路径的了 //用当前这个点更新其他点 for(int i = h[ver]; i != -1; i = ne[i]) { //获取到邻接表存放的结点，将这个结点数据存放到j中 int j = e[i]; //开始更新 if(dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j],j}); //把更新出来的数据插入到堆中 } } } } int main() { //输入 scanf("%d%d",&n,&m); //初始化邻接表 memset(h,-1,sizeof h); //根据m条边建图 while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } //调用dijkstra函数 dijkstra(); //输出 if(dist[n] == 0x3f3f3f3f) puts("-1"); else printf("%d",dist[n]); return 0; }
算法模板
堆优化版本的dijkstra算法操作流程可以下图表示：
堆优化版dijkstra算法代码描述如下：
typedef pair<int, int> PII; int n,m; // 点的数量 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储所有点到1号点的距离 bool st[N]; // 存储每个点的最短距离是否已确定 void dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); // first存储距离，second存储节点编号 while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); } } } }
细节落实
一、邻接表的建立
建立的思路是和建立静态链表一模一样的，只是要多记录一个权重，假如对静态链表不太熟悉的小伙伴可以看看这篇博客呀~
数据结构——竞赛好帮手，静态链表
二、建立小根堆的那行代码建议背下来
三、数据获取
获取到堆顶之后，还要继续通过first和second属性获取到相应的距离和结点编号等数据
/
