登录以参加训练计划
最短路径
dijkstra算法
Dijkstra算法是一种用于寻找图中两个节点之间的最短路径的算法。在这个过程中，我们通常会维护一个额外的数据结构来记录路径信息。这个数据结构通常是一个节点表，每个节点包含两个附加属性：前任节点和到起始节点的总距离。
基本步骤
-
初始化
- 为所有节点设置初始距离（通常设为无穷大）。
- 标记所有节点为未访问。
- 将源节点的初始距离设为0，并将其标记为已访问。
-
选择未访问节点中距离最短的节点进行处理。
-
对于选定的节点，遍历其所有邻居。
- 如果通过当前节点到达某个邻居节点的距离更短，则更新该邻居节点的距离，并将其前任节点设置为当前节点。
-
重复步骤2和3，直到所有节点都被处理过。
记录路径信息
在算法执行过程中，每当更新一个节点的距离时，都会记录下当前节点作为该节点的“前任节点”。这样，在算法结束时，如果需要找到从源节点到任何特定节点的路径，可以从该节点开始，沿着“前任节点”回溯，直到回到源节点，从而得到最短路径。
优化算法性能
为了优化算法的性能和准确性，可以使用优先队列（如最小堆）来高效地选择当前未访问节点中距离最短的节点进行处理。这种方法不仅适用于无向图，也适用于有向图的最短路径计算。
注意：Dijkstra算法假设图中没有负权重边，如果有负权重边则可能需要使用其他算法如贝尔曼-福特算法（Bellman-Ford algorithm）。
Bellman-Ford 算法
是一种用于计算加权图中单源最短路径的算法。它能够处理负权重边，并且可以检测负权重环（即权重和为负数的环）。与 Dijkstra 算法不同，Bellman-Ford 算法适用于存在负权重边的情况。
算法原理
Bellman-Ford 算法的核心思想是通过多次松弛操作来逐步更新从源点到所有其他顶点的最短路径估计值。具体步骤如下：
初始化：
将源点的距离设为 0。 将所有其他顶点的距离设为无穷大（或一个非常大的数）。
松弛操作：
对于图中的每一条边 (u, v) 和权重 w(u, v)，如果从 u 到 v 的距离可以通过经过 u 来缩短，则更新 v 的距离。 具体来说，如果 dist[v] > dist[u] + w(u, v)，则更新 dist[v] = dist[u] + w(u, v)。
重复松弛操作：
重复上述松弛操作 V-1 次（V 是图中顶点的数量），这样可以确保所有最短路径都被找到。
检测负权重环：
在进行 V-1 次松弛操作后，再进行一次松弛操作。如果在这次操作中仍然有顶点的距离被更新，说明图中存在负权重环。 算法步骤 假设图 G = (V, E) 有 V 个顶点和 E 条边，源点为 s。
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=100010;
int n,m,k,dist[N],backup[N];
struct Edge{
int a,b,c;
}mp[M];
int bellman(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=1;i<=k;i++){
memcpy(backup,dist,sizeof dist);
for(int j=1;j<=m;j++){
int a=mp[j].a,b=mp[j].b,c=mp[j].c;
dist[b] = min(dist[b],backup[a]+c);
}
}
if (dist[n]>0x3f3f3f3f/2) return -1;
else return dist[n];
}
int main(){
cin>>n>>m>>k;
int x,y,z;
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
mp[i]={x,y,z};
}
int r=bellman();
if (r==-1 && dist[n]>0x3f3f3f3f/2) cout<<"impossible"<<endl;
else cout<<dist[n];
return 0;
}
总结 适用性：Bellman-Ford 算法适用于存在负权重边的图，但不适用于存在负权重环的图。 时间复杂度：O(VE)，其中 V 是顶点数量，E 是边的数量。 优点：能够处理负权重边，并且可以检测负权重环。 缺点：时间复杂度较高，对于稠密图效率较低。 通过这个算法，你可以有效地计算单源最短路径，并检测图中是否存在负权重环。
floyed算法
Floyd-Warshall 算法的核心思想是通过逐步引入中间顶点来更新任意两个顶点之间的最短路径。具体来说，算法通过一个三维的迭代过程来更新最短路径矩阵 dist，其中 dist[i][j] 表示从顶点 i 到顶点 j 的最短路径长度。
初始化：
如果 i == j，则 dist[i][j] = 0。 如果存在直接连接顶点 i 和 j 的边，则 dist[i][j] 初始化为该边的权重。 否则，dist[i][j] = ∞（或一个非常大的数）。
动态规划更新：
对于每个顶点 k 作为中间顶点，检查通过 k 是否可以使 dist[i][j] 更小。 具体来说，如果 dist[i][j] > dist[i][k] + dist[k][j]，则更新 dist[i][j] = dist[i][k] + dist[k][j]。
检测负权重环：
在算法结束后，如果对于任何顶点 i，dist[i][i] < 0，则说明图中存在负权重环。
模版代码：
#include<iostream>
#include<cstring>
using namespace std;
const int N=205;
const int INF=0x3f3f3f3f;
int mp[N][N];
int n,m,q,dist[N];
bool v[N];
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
mp[i][j] = min(mp[i][j],mp[i][k]+mp[k][j]);
}
}
}
}
int main(){
memset(mp,0x3f,sizeof mp);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if (i==j) mp[i][j]=0;
else
mp[i][j] = INF;
}
}
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
mp[x][y]=min(mp[x][y],z);
}
floyd();
while(q--){
int a,b;
cin>>a>>b;
if (mp[a][b] > INF/2){
cout<<"impossible"<<endl;
}else{
cout<<mp[a][b]<<endl;
}
}
return 0;
}
SPFA算法:
SPFA（Shortest Path Faster Algorithm）是一种用于计算单源最短路径的算法，它是 Bellman-Ford 算法的一种优化版本。SPFA 算法通过使用队列来减少不必要的松弛操作，从而在大多数情况下比 Bellman-Ford 算法更快。SPFA 算法特别适用于稀疏图，并且可以处理负权重边。
算法原理
SPFA 算法的基本思想是：
使用一个队列来存储待处理的顶点。 从源点开始，将源点加入队列。 取出队列中的顶点，对其所有邻接点进行松弛操作。 如果某个邻接点的距离被更新了，则将该邻接点加入队列。 重复上述过程，直到队列为空。
算法步骤
假设图 G = (V, E) 有 V 个顶点和 E 条边，源点为 s。
初始化：
将源点的距离设为 0。 将所有其他顶点的距离设为无穷大（或一个非常大的数）。 将源点加入队列。 初始化一个布尔数组 inQueue，记录每个顶点是否在队列中。
松弛操作：
取出队列中的顶点 u。 对于 u 的每一个邻接点 v，如果 dist[v] > dist[u] + weight(u, v)，则更新 dist[v] 并将 v 加入队列（如果 v 不在队列中）。
检测负权重环：
如果某个顶点进入队列的次数超过 V 次，说明图中存在负权重环。
代码模版：
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10;
int n,m;
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;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx++;
}
int spfa(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
st[1]=true;
queue<int> q;
q.push(1);
while(q.size()){
int t=q.front();
q.pop();
st[t] = false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if (dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if (!st[j]){
q.push(j);
st[j]=true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
int main(){
cin>>n>>m;
int x,y,z;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
add(x,y,z);
}
int r=spfa();
if (r==-1 && dist[n]==0x3f3f3f3f) cout<<"impossible"<<endl;
else cout<<dist[n];
return 0;
}
判断是否存在负权回路的代码：
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 2e3 + 10, M = 1e4 + 10;
int n, m;
int head[N], e[M], ne[M], w[M], idx;
bool st[N];
int dist[N];
int cnt[N]; //cnt[x] 表示 当前从1-x的最短路的边数
void add(int a, int b, int c)
{
e[idx] = b;
ne[idx] = head[a];
w[idx] = c;
head[a] = idx++;
}
bool spfa(){
// 这里不需要初始化dist数组为 正无穷/初始化的原因是， 如果存在负环， 那么dist不管初始化为多少， 都会被更新
queue<int> q;
//不仅仅是1了， 因为点1可能到不了有负环的点， 因此把所有点都加入队列
for(int i=1;i<=n;i++){
q.push(i);
st[i]=true;
}
while(q.size()){
int t = q.front();
q.pop();
st[t]=false;
for(int i = head[t];i!=-1; i=ne[i]){
int j = e[i];
if(dist[j]>dist[t]+w[i]){
dist[j] = dist[t]+w[i];
cnt[j] = cnt[t]+1;
if(cnt[j]>=n){
return true;
}
if(!st[j]){
q.push(j);
st[j]=true;
}
}
}
}
return false;
}
int main()
{
cin >> n >> m;
memset(head, -1, sizeof head);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if (spfa()) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
return 0;
}
bellman-ford 和spfa的区别 1.Bellman-ford算法中，循环n次，每次遍历m条边，每次遍历的时候，把入度的点的距离更新成最小。 然而，这样就循环遍历了很多用不到的边。比如第一次遍历，只有第一个点的临边是有效的。
2.因此，spfa算法中，采用邻接表的方式，只用到有效的点（更新了临边的点），直到每个点都是最短距离为止。采用队列优化的方式存储每次更新了的点，每条边最多遍历一次。如果存在负权回路，从起点1出发，回到1距离会变小， 会一直在三个点中循环。
不用队列，遍历所有的点可以吗？
似乎不行，因为是更新了点之后，这个点的临边才可以用，如果没有更新到循环的点，那么循环的点也是不可用的。
spfa和dijkstra的区别： st用来检验队列中是否有重复的点 spfa从队列中使用了当前的点，会把该点pop掉，状态数组st[i] = false(说明堆中不存在了) ，更新临边之后，把临边放入队列中， 并且设置状态数组为true，表示放入队列中 。如果当前的点距离变小，可能会再次进入队列，因此可以检验负环：
每次更新可以记录一次，如果记录的次数 > n,代表存在负环（环一定是负的，因为只有负环才会不断循环下去）。
st是一个集合，不是检验队列中的点。 dijkstra使用当前点更新临边之后，把该点加入到一个集合中，使用该点更新临边，并把临边节点和距离起点的距离置入堆中（不设置状态数组）。下一次从堆中取最小值，并把对应的节点放入集合中，继续更新临边节点，直到所有的点都存入集合中。因此dijkstra不判断负环。
从上述描述中能看出，dijkstra存放节点的堆，具有单调性，而spfa的队列不需要具有单调性。
最小生成树
最小生成树（Minimum Spanning Tree, MST）是一个有n个结点的连通图的生成树，这个生成树是原图的极小连通子图，包含原图中的所有n个结点，并且有保持图连通的最少的边。最小生成树可以用Kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。最小生成树具有以下性质：它的边数等于顶点数减1，且树内一定不会有环。对于给定的图，其最小生成树可以不唯一，但其边权值之和一定唯一。最小生成树是在无向图生成的，故其根节点可以是树上任意节点。
最小生成树问题（minimal spanning tree problem）是求解连通无向图的权最小的生成树。生成树的权（权可以表示距离、时间、费用等）为树的所有的边的权之和。具有最小权的生成树称为图的最小生成树。
简而言之，最小生成树是指在连通图中所有可能的生成树中，边的权值之和最小的那棵树。它是图论中的一个重要概念，广泛应用于需要优化网络连接、电路设计等实际问题中。
给定一个无向图，在图中选择若干条边把图的所有节点连起来。要求边长之和最小。在图论中，叫做求最小生成树。
最小生成树：把连通的图的所有顶点连起来路径之和最小的问题，即生成树总权值之和最小。
最短路：把两点之间路径最短。 最短路只是需要将两个点连起来，其路径并不一定经过所用点，而最小生成树要连接每一个点。
prim算法
prim 与 dijkstra 思路区别
dijkstra：把所有点到 源点 距离dis设成∞ ，每次找到dis最小的点 确定下来(加入到路径中)，并用该点距离更新所有点到源点距离 dis[i]=min(dis[i],w+a[t][i]); 即：用源点扩展，每次确定距离最近的点，直到终点！！
prim： : 把所有点到 集合 的距离dis设成∞ ，每次找到dis最小的点 确定下来(加入到集合中)，并用该点距离更新所有点到集合距离 dis[i]=min(dis[i],a[t][i]); 即：随意找一个起点，每次确定到集合最近的点，直到所有点都确定完！！
由上面的思路区别，不难看出唯一区别就是，dijkstra 更新的是到源点的距离，prim更新的是到集合的距离。
prim 与 dijkstra 代码区别
由上面可知 dijkstra和prim 的唯一区别，那是不是只需要将dijkstra代码中的 dis 更改成到集合的距离就可以了（特别注意需要将已经确定的点的dis不再被改变）
代码样例
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int g[N][N],n,m,dist[N];
bool st[N];
int prim(){
int res=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if (!st[j] && (t==-1 || dist[j]<dist[t]))
t=j;
}
if (i && dist[t]==INF) return INF;
if (i) res+=dist[t];
st[t]=true;
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],g[t][j]);
}
}
return res;
}
int main(){
cin>>n>>m;
memset(dist,0x3f,sizeof dist);
memset(g,0x3f,sizeof g);
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
g[x][y]=g[y][x]=min(g[x][y],z);
}
int r=prim();
if (r==INF) cout<<"impossible"<<endl;
else cout<<r<<endl;
return 0;
}
kruscal算法
算法思路：
1.将所有边按照权值的大小进行升序排序，然后从小到大一一判断。
2.如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。
3.直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。
4.筛选出来的边和所有的顶点构成此连通网的最小生成树。
判断是否会产生回路的方法为：使用并查集。
1.在初始状态下给各个个顶点在不同的集合中。、
2.遍历过程的每条边，判断这两个顶点的是否在一个集合中。
如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边不要。如果不在一个集合中，则要这条边。
kruscal算法样例
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m;
struct Edge{
int a,b,w;
}g[N];
int p[N];
bool compair(const Edge &a,const Edge &b){
return a.w<b.w;
}
int find(int x){
int r=x;
while(r!=p[r]){
r=p[r];
}
while (r!=x){
int t=x;
x=p[x];
p[t]=r;
}
}
int main(){
int res=0,cnt=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
p[i]=i;
}
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
g[i]={x,y,z};
}
sort(g+1,g+1+m,compair);
for(int i=1;i<=m;i++){
int a=g[i].a,b=g[i].b,c=g[i].w;
int x=find(a),y=find(b);
if (x!=y){
res+=c;
cnt++;
p[x]=y;
}
}
if (cnt<n-1) {
cout<<"impossible"<<endl;
} else{
cout<<res<<endl;
}
return 0;
}
- 参加人数
- 2
- 创建人
-
junnyfan