ACM寒假集训第三四五天：最短路（Dijkstra、Bellman-Ford、SPFA、Floyd）基础建图模型

95 阅读 0 评论 63 点赞

我是靠谱客的博主激昂蜜粉，最近开发中收集的这篇文章主要介绍ACM寒假集训第三四五天：最短路（Dijkstra、Bellman-Ford、SPFA、Floyd）基础建图模型，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Floyd算法是多源最短路算法，复杂度最高（n^3），通常用在点比较少的起点不固定的问题中。能解决负边（负权）但不能解决负环。

Dijkstra算法是单源最短路算法，最常用时间复杂度（n^2）优化后可以达到（nlogn），不能解决负边问题，稀疏图（点的范围很大但是边不多，边的条数|E|远小于|V|²）需要耗费比较多的空间。

算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间要低。

SPFA算法适合稀疏图，可以解决带有负权边，负环的问题，但是在稠密图中效率比Dijkstra要低。

Floyd：

核心代码只有几行：

   for(int k=1;k<=n;k++)
   {
       for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=n;j++)
           {
               map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
           }
       }
   }

可以找多源最短路，时间复杂度高。

下面是完整代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
const int maxn = 105;
int map[maxn][maxn];
using namespace std;
int main()
{
int n, m, a, b, c, str, end;
//点，边，路径与权，开始坐标，结尾坐标
cin >> n >> m;
for (int i = 1; i <= n; i++){
//图的初始化，对角线（即本身到本身）为0，其余为无穷
for (int j = 1; j <= n; j++){
if (i == j) map[i][j] = 0;
else map[i][j] = inf;
}
}
for (int i = 1; i <= m; i++){
//记录路径
cin >> a >> b >> c;
if (map[a][b] > c){
//重复输入保存最小值
map[a][b] = map[b][a] = c;
}
}
cin >>str >> end;
//开始，结尾坐标
for (int k = 1; k <= n; k++){
//k在最外层
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
}
}
}
cout << map[str][end] << endl;
return 0;
}

Dijkstra：

只能计算单元最短路，不能计算负权值，贪心思想。开一个dis数组用来存储起始点到其他点的最短路，初始化时存的是起始点到其它点的初始路程，通过n-1遍的遍历找最短。例如1到3的最短路就是比较dis[3]与dis[2]+map[2][3]的值。另外开辟一个book数组用来标记已经找过的最短路。

下面是完整代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
const int maxn = 105;
int map[maxn][maxn], dis[maxn], book[maxn];
//图，最短路，记录
using namespace std;
int main()
{
memset(book, 0, sizeof(book));
int n, m, a, b, c, u, v, Min;
//点，边，路径和权，Min下面求最短路用
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (i == j) map[i][j] = 0;
//图的初始化
else map[i][j] = inf;
}
}
for (int i = 1; i <= m; i++){
cin >> a >> b >> c;
if (map[a][b] > c){
map[a][b] = map[b][a] = c;
}
}
for (int i = 1; i <= n; i++){
//距离初始为到i的权
dis[i] = map[1][i];
}
book[1] = 1;
//1到1默认走过
for (int i = 1; i < n; i++){
Min = inf;
//Min初始为无穷大
for (int j = 1; j <= n; j++){
if (book[j] == 0 && dis[j] < Min){
//判断是否标记以及是否可走（不可走为无穷）
Min = dis[j];
book[j] = 1;
u = j;
}
}
for (int v = 1; v <= n; v++){
//求最短路
if (map[u][v] < inf){
dis[v] = min(dis[v], dis[u] + map[u][v]);
}
}
}
for (int i = 1; i <= n; i++){
//输出每个最短路
cout << dis[i] << " ";
}
return 0;
}

Bellman-Ford：

怎样判断负权回路？

当进行n-1次循环之后，仍然可以运行核心代码部分交换值（if判断语句内的内容）则一定形成负权回路。

#include <iostream>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int MAX=105;
int u[MAX],v[MAX],w[MAX],dis[MAX];
int main()
{
int n,m,check,flag;
//顶点个数，边数 ,检验是否可以退出循环，负权回路判断
cin>>n>>m;
for(int i=1;i<=m;i++)
//读入边
{
cin>>u[i]>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
//1号点到各个点的初始位置设为无穷
{
dis[i]=inf;
}
dis[1]=0;
for(int k=1;k<=n-1;k++)
//Bellman-Ford算法核心
{
check=0;
for(int i=1;i<=m;i++)
{
if(dis[v[i]]>dis[u[i]]+w[i])
{
dis[v[i]]=dis[u[i]]+w[i];
check=1;
}
}
if(check==0)
//若不再更新则可以退出
{
break;
}
}
flag=0;
for(int i=1;i<=m;i++)
//判断负权回路
{
if(dis[v[i]]>dis[u[i]]+w[i])
{
flag=1;
}
}
if(flag==1)
{
cout<<"存在负权回路"<<endl;
}
else
{
cout<<"不存在负权回路"<<endl;
}
for(int i=1;i<=n;i++)
//输出1到各点距离
{
cout<<dis[i]<<" ";
}
return 0;
}
/*5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3*/

Spfa（Bellman-Ford的队列优化）：

#include <iostream>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int MAX=1e3+5;
int u[MAX],v[MAX],w[MAX],first[MAX],next[MAX],dis[MAX],book[MAX];
//起始，终止，权，此值的最后一条边的存储位置，此值的上一条边的存储位置，距离，记录
int main()
{
int n,m;
//点，边
cin>>n>>m;
memset(dis,0x3f,sizeof(dis));
//距离初始无穷
dis[1]=0;
//1-1初始为0
memset(book,0,sizeof(book));
//清空记录数组
for(int i=1;i<=n;i++)
//初始-1
{
first[i]=-1;
}
for(int i=1;i<=m;i++)
//读入图
{
cin>>u[i]>>v[i]>>w[i];
next[i]=first[u[i]];
//链式前向星
first[u[i]]=i;
}
int que[MAX]={0},head=1,tail=1,k; //队列，头，尾
que[tail]=1,tail++;
//1号顶点入队
book[1]=1;
//入队标记
while(head<tail)
//队列不为空的时候循环
{
k=first[que[head]];
//当前需要处理的首顶点
while(k!=-1)
//扫描当前所有的边
{
if(dis[v[k]]>dis[u[k]]+w[k])
//判断是否松弛
{
dis[v[k]]=dis[u[k]]+w[k];
//更新值
if(book[v[k]]==0)
//用数组记录顶点v[k]是否在队列中，不然每次都要从head-tail扫一遍
{
que[tail]=v[k];
//入队
tail++;
book[v[k]]=1;
}
}
k=next[k];
}
book[que[head]]=0;
//出队
head++;
}
for(int i=1;i<=n;i++)
//输出所有1-i的最短距离
{
cout<<dis[i]<<" ";
}
return 0;
}
/*
5 7
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6
0 2 5 9 9 */

queue实现：

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int MAX=1e3+5;
struct point
{
int to,next,d;
};
point a[MAX];
int head[MAX];
int main()
{
int n,m,x,y,d;
cin>>n>>m;
int cnt=0;
memset(head,0,sizeof(head));
for(int i=1;i<=m;i++)
//存图
{
cin>>x>>y>>d;
a[++cnt].next=head[x];
a[cnt].to=y;
a[cnt].d=d;
head[x]=cnt;
a[++cnt].next=head[y];
a[cnt].to=x;
a[cnt].d=d;
head[y]=cnt;
}
int v0=1;
//这里是从1，不是head[1]
int book[MAX],dis[MAX];
memset(book,0,sizeof(book));
memset(dis,0x3f,sizeof(dis));
book[v0]=1;
queue<int>q;
q.push(v0);
dis[v0]=0;
while(!q.empty())
//非空循环
{
int u=q.front();
//当前需要处理的元素
q.pop();
//出队
book[u]=0;
for(int i=head[u];i;i=a[i].next)
{
int v=a[i].to;
if(dis[v]>dis[u]+a[i].d)
//松弛
{
dis[v]=dis[u]+a[i].d;
if(book[v]==0)
{
q.push(v);
//进队
book[v]=1;
}
}
}
}
for(int i=1;i<=n;i++)
//输出所有1-i的最短距离
{
cout<<dis[i]<<" ";
}
return 0;
}
/*
5 7
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6
0 2 5 9 9 */