【C/C++】最短路径
2024-09-06 20:47:01
BFS求无权图的最短路径
用book数组的值表示路径长度即可，省略
Floyd算法（允许负边）
- Floyd算法可以一次性求出所有节点之间的最短距离，且代码简单，但是时间复杂度达到了n^3，因此只适用于n<200的情况；
- 原理：任意两点i，j之间的距离分为两种情况：过k点和不过k点。从k=1开始操作遍历到n即可，不过很显然每次计算基本上只有对k的邻边是有效的
- 代码实现（基于邻接矩阵）：
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 105;
int graph[MAXN][MAXN];
void floyd(int n)
{
int s=1;//求s到n的距离
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
if(graph[i][k] != INF)//如果相等则说明无需遍历
for(int j=1; j<=n; j++)
if(graph[i][j] > graph[i][k] + graph[k][j])
graph[i][j] = graph[i][k] + graph[k][j];
printf("%d\n",graph[s][n]);//输出结果
return ;
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
if(n==0 && m==0) break;
memset(graph,0x3f,sizeof(graph));
while(m--)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
graph[a][b] = graph[b][a] = c;
}
floyd(n);
}
return 0;
}
- Floyd算法适用于邻接矩阵：由于算法是动态规划的思想，必须有一个二维数组表示点与点之间的距离，所以使用其他图的表示方法会浪费空间；
- 判断负圈：通过代码不难发现，点 i 到自己的距离并非为0，而是graph[i][i] = graph[i][k] + graph[k][i]，即绕外面一圈再回来。一旦存在graph[i][i]<0，就说明有负圈存在；
Bellman-Ford算法（允许负边）
- Bellman-Ford算法解决的是单源最短路径问题，即起点s到图中每个点的最短距离；
- 原理：每一轮更新中，对于每一个点，询问它的邻居是否可以到达s点：如果可以，当前的点就可以通过邻居到达s点。不难想象，每一轮更新中至少有一个点到s的最短距离可以被确定下来，所以一共需要更新n轮，时间复杂度为O(n*m);
- 图的表示方式：如果使用邻接矩阵，遍历边的过程依然为O(n*n)，并没有得到优化，因此使用数组存边或者邻接表来存图；
- 代码实现：
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e3 + 10;
struct edge{int u, w, v; } e[MAXN*2];
int pre[MAXN],d[MAXN];//pre存放前置节点，d[i]存放s到点i的距离
void Print_path(int s, int t)//打印s到t的最短路径
{
if(s == t) printf("%d",s);
else
{
Print_path(s,pre[t]);
printf(" %d",t);
}
}
void bellman(int n, int cnt)
{
int s = 1;//s为起点
memset(d,0x3f,sizeof(d));//初始化为最大值
d[s] = 0;//s到自己的距离为0
for(int k=1; k<=n; k++)
for(int i=0; i<cnt; i++)
{
int x = e[i].u, y = e[i].v;
if(d[x] > d[y] + e[i].w)
{
d[x] = d[y] + e[i].w;
pre[x] = y;
}
}
printf("%d\n",d[n]);//打印s到n的最短距离
Print_path(s,n);
printf("\n");
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
int cnt = 0;
while(m--)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
e[cnt].u = a; e[cnt].v = b; e[cnt].w = c; cnt++;
e[cnt].v = a; e[cnt].u = b; e[cnt].w = c; cnt++;
}
bellman(n,cnt);
}
return 0;
}
- 判断负圈：很明显当负圈存在时，程序会一直存在距离更新，因此要判断循环次数是否超过了n，如果超过说明有负圈；
- 优化后的代码：
bool bellman(int n, int cnt)
{
int s = 1;//s为起点
memset(d,0x3f,sizeof(d));//初始化为最大值
d[s] = 0;//s到自己的距离为0
bool updata = true;//updata表示上一轮有没有更新，如果有则继续更新，否则停止更新
int k = 0;//k表示循环次数
while(updata)
{
updata = false;//当前一轮还未进行过更新
k++;
if(k>n) return false;//循环次数超过n则返回有负圈
for(int i=0; i<cnt; i++)
{
int x = e[i].u, y = e[i].v;
if(d[x] > d[y] + e[i].w)
{
updata = true;//发生了更新操作
d[x] = d[y] + e[i].w;
pre[x] = y;
}
}
}
printf("%d\n",d[n]);//打印s到n的最短距离
Print_path(s,n);
printf("\n");
return true;
}
SPFA算法（允许负边）
- SPFA是对Bellman-Ford算法的优化。在Bellman-Floyd算法每一轮的更新中，如何确定当前节点v需不需要更新？很明显，当且仅当v的邻居节点的最短路径发生变动的时候，节点v才需要更新。SPFA算法使用BFS的思想，把需要更新的节点放进队列中，当队列为空时，算法结束。
- 判断负圈：节点每进入一次队列即为当前节点更新了一次，由Bellman-Ford算法中的结论可知，当存在一个节点更新次数超过n次时，说明一定有负圈。
- 代码实现(：
//基于邻接表
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 10;
struct edge
{
int to,w;
};
vector<edge>e[MAXN];
int pre[MAXN];//记录路径
bool inq[MAXN];//是否在队列内，优化用
int Neg[MAXN];//记录循环次数判断负圈
int dis[MAXN];//记录最短距离
void print_path(int s, int t)//递归输出最短路径
{
if(s == t) {printf("%d",s); return ;}
print_path(s, pre[t]);
printf(" %d",t);
}
void print_path2(int s, int t)//非递归的路径输出，适用于极端情况
{
stack<int>ans;
while(s!=t)
{
ans.push(t);
t = pre[t];
}
printf("%d",s);
while(!ans.empty())
{
printf(" %d",ans.top());
ans.pop();
}
printf("\n");
}
bool spfa(int s, int n)
{
memset(dis,0x3f,sizeof(dis));
memset(inq,false,sizeof(inq));
memset(Neg,0,sizeof(Neg));
Neg[s] = 1;
inq[s] = true;
dis[s] = 0;
queue<int>Q;
Q.push(s);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
inq[u] = false;
for(int i=0; i<e[u].size(); i++)
{
int v = e[u][i].to;
int w = e[u][i].w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
pre[v] = u;
if(!inq[v])
{
inq[v] = true;
Q.push(v);
Neg[v]++;
if(Neg[v] > n) return false;//返回值为false代表有负圈
}
}
}
}
printf("%d\n",dis[n]);
print_path2(s,n);
return true;
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
for(int i=0; i<m; i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
edge t = {b,c};
e[a].push_back(t);
}
spfa(1,n);
}
return 0;
}
//基于链式前向星的SPFA算法
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int NUM = 1e6 + 10;
struct Edge
{
int to,next,w;
}edge[NUM];
int cnt;
int head[NUM];
int dis[NUM];
bool inq[NUM];
int Neg[NUM];
int pre[NUM];
void print_path(int s,int t)//打印起点s到t的最短路径
{
stack<int>ans;
while(t!=s)
{
ans.push(t);
t = pre[t];
}
printf("%d",s);
while(!ans.empty())
{
printf(" %d",ans.top());
ans.pop();
}
printf("\n");
}
void init()//前向星的初始化
{
for(int i=0; i<NUM; i++)
{
edge[i].next = -1;
head[i] = -1;
}
cnt = 0;
}
void addedge(int u, int v, int w)//前向星的加边操作
{
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
bool spfa(int s, int n)
{
memset(inq,false,sizeof(inq));
memset(dis,0x3f,sizeof(dis));
memset(Neg,0,sizeof(Neg));
Neg[s] = 1;
dis[s] = 0;
inq[s] = true;
queue<int>Q;
Q.push(s);
while(!Q.empty())
{
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v = edge[i].to; int w = edge[i].w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
pre[v] = u;
if(!inq[v])
{
Q.push(v);
inq[v] = true;
Neg[v]++;
if(Neg[v] > n) return false;
}
}
}
}
printf("%d\n",dis[n]);
print_path(s, n);
return true;
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
init();
while(m--)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
addedge(a, b, c);
}
spfa(1, n);
}
return 0;
}
Dijkstra算法（无法求负边）
- Dijkstra算法应用了贪心的思想，即从起点开始抄近路走。类似于多米诺骨牌，即从起点开始推倒骨牌，当节点第一次被到达时最短路径被确定。
- 代码借助STL中的优先队列完成，每次取出到S距离最短的节点来模拟多米诺骨牌模型。
//基于邻接表
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int NUM = 1e5;
struct edge
{
int from, to, w;
edge(int a, int b, int c)
{
from = a;
to = b;
w = c;
}
};
vector<edge>e[NUM];
struct s_node
{
int id, n_dis;
s_node(int b, int c)
{
id = b;
n_dis = c;
}
bool operator < (const s_node & a) const
{
return n_dis > a.n_dis;
}
};
int dis[NUM];
bool done[NUM];
int pre[NUM];//记录前驱结点
void print_path(int s, int t)
{
stack<int>ans;
while(s != t)
{
ans.push(t);
t = pre[t];
}
printf("%d",s);
while(!ans.empty())
{
printf(" %d",ans.top());
ans.pop();
}
printf("\n");
}
void dijkstra(int s,int n)
{
memset(dis, 0x3f, sizeof(dis));
memset(done, false, sizeof(done));
dis[s] = 0;
priority_queue<s_node>Q;
Q.push(s_node(s, dis[s]));
while(!Q.empty())
{
s_node u = Q.top();
Q.pop();
if(done[u.id])
continue;
done[u.id] = true;
for(int i=0; i<e[u.id].size(); i++)
{
edge y = e[u.id][i];
if(done[y.to])
continue;
if(dis[y.to] > y.w + u.n_dis)
{
dis[y.to] = y.w + u.n_dis;
Q.push(s_node(y.to, dis[y.to]));
pre[y.to] = u.id;
}
}
}
printf("%d\n",dis[n]);
print_path(s, n);
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
if(n==0 && m==0) break;
for(int i=1; i<=n; i++)
e[i].clear();
while(m--)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
e[a].push_back(edge(a,b,c));
e[b].push_back(edge(b,a,c));
}
dijkstra(1, n);
}
return 0;
}
最新文章
- 【2016-10-27】【坚持学习】【Day14】【GlobalAssemblyInfo 】
- Gym 101102D---Rectangles(单调栈)
- java常用类 --- Object
- [转自Kevins的天空 http://rootsec.cn]rad studio 2007 up3方法
- ubuntu 的 apt-get update 出现404错误时，ubuntu 版本也 end of life 了的解决方案
- win7下.NET 2.0未在web服务器上注册的问题(转）
- Delphi Windows API判断文件共享锁定状态（OpenFile和CreateFile两种方法）
- jQuery事件大全
- spring整合JMS - 基于ActiveMQ实现
- SpringMVC:学习笔记(1)——理解MVC及快速入门
- Java重载重写与实现方法的规则
- Swift如何取得View所属的ViewController
- web报表工具FineReport使用中遇到的常见报错及解决办法（二）
- 程序到CPU的路径
- 报错：[Vue warn]: Avoid mutating a prop directly since the value will be overwritten whenever the parent component re-renders. Instead, use a data or computed property based on the prop's value. Prop bei
- oracle 数据库备份expdp、impdp
- mysql 开发进阶篇系列 19 MySQL Server(innodb_flush_log_at_trx_commit与sync_binlog)
- 【vue】vue +element 搭建项目，使用el-date-picker组件遇到的坑
- UICollectionViewController的用法1
- javascript中的getter和setter