数据结构——最短路(BFS,Dijkstra,Floyd)

完整版可以看我的最短路问题模版总结_稠密图最短路-CSDN博客

考研数据结构只考BFS,Dijkstra和Floyd

下面代码以Acwing模板题为例

BFS代码

适用类型：

1.单源最短路径

2.无权图

3.不适用于带权图和负权回路图

//Acwing走迷宫bfs
#include<bits/stdc++.h>using namespace std;const int N = 110;typedef pair<int,int> PII;int g[N][N];bool st[N][N];int dx[4]={-1,0,1,0};int dy[4]={0,-1,0,1};int n,m;int ans[N][N];void bfs(int x,int y)
{queue<PII> q;q.push({x,y});while(!q.empty()){auto t = q.front();q.pop();for(int i=0;i<4;i++){int nex = t.first + dx[i];int ney = t.second + dy[i];if(nex>=1&&nex<=n&&ney>=1&&ney<=m&&!st[nex][ney]&&g[nex][ney]==0){q.push({nex,ney});ans[nex][ney]=ans[t.first][t.second]+1;st[nex][ney]=true;}}}
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>g[i][j];}}bfs(1,1);cout<<ans[n][m]<<endl;return 0;
}

Dijkstra代码（O(n^2))

适用类型：

1.单源最短路径

2.正权图

3.不适用于负权图和负权回路图

#include <bits/stdc++.h>using namespace std;
#define fs first
#define sc second
#define endl '\n'
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int, int> PII;const int N = 510;int dist[N];//dist[i]表示i号点到源点的距离int st[N];//表示一个最短路径的点集合 若为1表示在集合中 若为0表示不在集合中 全局初始为0int g[N][N];//邻接矩阵存储int n,m;//点和边int Dijkstra()
{//初始化memset(dist,0x3f,sizeof(dist));//memset按字节赋值 赋值完是0x3f3f3f3fdist[1]=0;for(int i=1;i<=n;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||dist[j]<dist[t])){t=j;}}//内层循环执行完后便找到了在集合st外距离源点(这里默认为1)最近的点st[t]=1;//加入集合//用t来更新距离for(int k=1;k<=n;k++){dist[k]=min(dist[k],dist[t]+g[t][k]);}}if(dist[n]==0x3f3f3f3f)return -1;//1——>n不连通return dist[n];
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);memset(g,0x3f,sizeof(g));cin>>n>>m;for(int i=0;i<m;i++){int a,b,c;cin>>a>>b>>c;g[a][b]=min(g[a][b],c);}cout<<Dijkstra()<<endl;return 0;
}

Floyd代码 （O(n^3))

适用类型：

1.多源最短路径

2.正、负权图

3.适用于负权，不适用于负权回路图

#include <iostream>
using namespace std;const int N = 210, M = 2e+10, INF = 1e9;int n, m, k, x, y, z;
int d[N][N];void floyd() {for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}int main() {cin >> n >> m >> k;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(i == j) d[i][j] = 0;else d[i][j] = INF;while(m--) {cin >> x >> y >> z;d[x][y] = min(d[x][y], z);//注意保存最小的边}floyd();while(k--) {cin >> x >> y;if(d[x][y] > INF/2) puts("impossible");else cout << d[x][y] << endl;}return 0;
}