8.6 图 最短路与Djkstra+模拟ACM总结

8.6 图 最短路与Djkstra+模拟ACM总结

目录

• 图
• • 图的分类
  • 图的存储
  • • 邻接矩阵
    • 邻接表
• Dijkstra算法
• • 算法思想
  • 代码实现
• 模拟ACM周赛总结
• • CF1146A
  • CF1681B
  • P2347
  • P3905

图

图是有顶点集合(Vertex)及顶点间的关系集合(Edge)组成的一种数据结构。

图的分类

有向图
顶点 i 与顶点 j 之间的边有指向方向的图，称为有向图。

无向图
顶点 i 与顶点 j 之间的边没有指向方向的图，称为有向图。
无向图也可以用有向图表示。
如：顶点 i 与顶点 j 之间有两条边，一条i->j ，另一条j<-i，可以看作无向图。

稠密图
顶点n的数量，远小于边数m，一般 m m m ≥ n 2 n^2 n2。

稀疏图
顶点n的数量， 与边数m在同一数量级。如n = 9999, m = 10001。

权
顶点 i 与顶点 j 之间的边有长度，长度称为权。

重边
顶点 i 与顶点 j 之间的边有不止1条，这时， 取权最小的那一条边。

自环
一个顶点，自己与自己相连。

图的存储

邻接矩阵

对于稠密图，点数一般不会越界，可以使用邻接矩阵（即二维数组）存储。

邻接矩阵=二维数组，数组 [i] [j] 存储的即为 i 顶点到 j 顶点的边权。
在读入数据之前，我们还要初始化 [i] [j]为INF，即无穷大，因为读入数据以前没有边，每个顶点都永远走不到其它顶点。
如果 i 等于j, 即顶点自己到自己，存储长度为0。

贴代码：

//图的存储
const int N=1005;
int G[N][N];//初始化
G = memset(G,0x3f,sizeof(G));
for(int 1=0;i<=n;i++)
{for(int j=1;j<=n;j++){if(i==j) G[i][j]=0;//自己到自己的路径长度为0 }
} //读入 
for(int i=1;i<=m;i++)
{int x,y,k;cin>>x>>y>>k;G[x][y]=min(G[x][y],k);//如果有重边，取最短的 
}

邻接表

对于稀疏图，如果点数与边数一样大则会导致数组越界。考虑邻接表存储。
v e c t o r vector vector
用动态二维数组存储图，可以节省没有使用的空间防止MLE。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;const int N=1005;
int n,m;//节点数，边数 struct Node{int to;//节点 int w;//边权 
};
vector<Node> g[N];
//有多少个节点就有多少个动态数组，第i个动态数组中存它的所有邻居节点。
//本质上v数组是一个二维数组。 void add(int f,int to,int w) 
{g[f].push_back({to,w});//存储 return;
}int main()
{cin>>n>>m;for(int i=1;i<=m;i++){int f,to,w;cin>>f>>to>>w;add(f,to,w);}return 0;
}

除了动态数组存储，也可以使用链表，以及一维数组模拟邻接表存储。

Dijkstra算法

算法思想

设置两个数组，一个数组dis[]存储距离，一个数组st[]存储状态。

n个结点，在搜索前的初始路径都是无穷大。记录最短路径的前面的结点的数组，此时都为空。

每次从未标记的结点中，选择距离出发点最近的结点，标记st，收录到最优解。

计算刚加入结点a的临近节点的b的距离。（未标记结点）

如果(结点a的距离+a->b||b<-a) < 结点b的距离，更新结点b的距离，以及前面点。

可以画表格辅助理解。

代码实现

这里，我们使用优先队列priority_queue进行优化。

#include<bits/stdc++.h>
using namespace std;typedef pair<int,int> PII;//存储距离，结点 vector<vector<pair<int, int>> > g;const int N=1005;
int dis[N],st[N];void add(int f,int to,int w) 
{g[f].push_back({to,w});return;
}int dijkstra(int n)
{memset(dis,0x3f,sizeof(dis));//初始距离都为INFdis[1]=0;//原点到原点的距离为0 priority_queue<PII, vector<PII>, greater<PII> > q;//小根堆，头元素为最小值q.push({0,1});//推入21行 while(q.size()){PII t&#p();//取距离原点最近的点 q.pop();//弹出头元素int x=t.second,y=t.first; //x=节点编号，y=结点距离原点距离。 if(st[x]) continue; //如果这个结点被标记过，证明这条路已经走过了，不重复走了 st[x] = true;
//没有确定最短路径的节点中距离源点最近的点，找到了源点到该节点的最短距离，标记 for(int i = 0;i<g[x].size();i++)//遍历i可以到达的所有节点 {int newto = g[x][i].first;//重复31行往下的步骤 int neww = g[x][i].second;if (dis[newto] > dis[x] + neww) {//如果新的距离小于原有距离，更新 dis[newto] = dis[x] + neww;q.push({dis[newto], newto});//推入更新后的pair }} }	if (dis[n] == 0x3f3f3f3f) return -1;//如果没有路，返回-1 return dis[n];//如果被更新了，存在路径 
}int main()
{int T;cin>>T;while(T--){int n,m,k;cin>>n>>m>>size(n+1);while(m--){int f,to,w;cin>>f>>to>>w;add(f,to,w);}cout<<dijkstra(n);}return 0;
}

模拟ACM周赛总结

CF1146A

纯数学题，推公式即可。

CF1681B

也是找规律的题。编数据时要考虑全面，要包含特殊情况与大数，避免因为int太小，没开long long而导致WA或RE的错误。不要固化思维。

P2347

一道多重背包的模板题，根据样例，将问题转换成背包问题即可。

P3905

Djkstra模板题，看懂样例即可。