问题描述
给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
输入格式
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
输出格式
共n-1行，第i行表示1号点到i+1号点的最短路。
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
-2
数据规模与约定
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。
dfs只能处理两点之间的最短路径，且可能超时，bfs只能处理所有边的权值一样的
Floyd算法适合稠密图，而且可以解决负权边，但是时间复杂度高
Dijkstra算法适合稠密图，但是不能解决负权边
Forf算法适合稀疏图，可以解决负权边
dlikstra又不能处理带负权的问题
dlikstra算法
#include<iostream> #define inf 0x333f #define maxn 200 using namespace std; int main() { int dis[maxn],book[maxn],e[maxn][maxn],n,m,a,b,v,min,flag;//n表示顶点，m表示边 cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) e[i][j]=0; else e[i][j]=inf; } } for(int i=1;i<=m;i++) { cin>>a>>b>>v; e[a][b]=v; } for(int i=1;i<=n;i++) { dis[i]=e[1][i]; } for(int i=1;i<=n;i++) { book[i]=0; } book[1]=1; //找到离单源最短的顶点 min=inf; for(int i=1;i<n;i++) { min=inf; for(int j=1;j<=n;j++) { if(book[j]==0&&dis[j]<min) { min=dis[j]; flag=j; } } book[flag]=1; for(int k=1;k<=n;k++) { if(e[flag][k]<inf) { if(dis[k]>dis[flag]+e[flag][k]) dis[k]=dis[flag]+e[flag][k]; } } } for(int i=2;i<=n;i++) cout<<dis[i]<<endl; return 0; }
使用Floyd算法再使用邻接矩阵存储数据
会即超时又超内存
#include<iostream> #include<algorithm> #define inf 0x333f using namespace std; int n,m,a[2000][2000],v0,v1,v; int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=inf; for(int i=1;i<=n;i++) a[i][i]=0; for(int i=1;i<=m;i++) { cin>>v0>>v1>>v; a[v0][v1]=v; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(a[i][k]<inf&&a[k][j]<inf&&a[i][k]+a[k][j]<a[i][j]) a[i][j]=a[i][k]+a[k][j]; } for(int i=2;i<=n;i++) cout<<a[1][i]<<endl; return 0; }
且看bellman-ford算法加邻接表大显身手
#include<iostream> using namespace std; const int inf=2000; const int maxn=20000; int main() { int n,m,u[maxn],v[maxn],w[maxn],dis[maxn],flag; cin>>n>>m; for(int i=1;i<=m;i++) { cin>>u[i]>>v[i]>>w[i]; } for(int i=2;i<=n;i++) dis[i]=inf; dis[1]=0; for(int k=1;k<=n-1;k++) { flag=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]; flag=1; } } if(flag) break; } for(int i=2;i<=n;i++) cout<<dis[i]<<endl; return 0; }
。。。。。。
再见
————————————————————————————————
来个带队列优化的bellman-ford算法(SPFA-shortest path faster algorithm)
#include <cstdio> #include <string> #include <vector> #include <queue> #include <string.h> #define MAX 20000 + 10 #define INF 0x3fffffff using namespace std; typedef struct { int v; int l; } Edge; vector<Edge> MGraph[MAX]; int dist[MAX]; int visit[MAX]; int inq[MAX]; int num[MAX]; bool SPFA( int s, int n ) { // 初始化部分 memset( inq, false, sizeof( inq ) ); memset( num, 0, sizeof( num ) ); fill( dist, dist + MAX, INF ); // 源点入队部分 queue<int> Q; Q.push( s ); // 源点入队 inq[s] = true; // 源点已入队 num[s]++; // 源点入队次数加1 dist[s] = 0; // 主体部分 while( !Q.empty() ) { int u = Q.front(); // 队首顶点编号为u Q.pop(); inq[u] = false; // 设置u不在队列中 // 遍历u的所有邻接边v for( int j = 0; j < MGraph[u].size(); j++ ) { int v = MGraph[u][j].v; int dis = MGraph[u][j].l; // 松弛操作 if( dist[u] + dis < dist[v] ) { dist[v] = dist[u] + dis; if( !inq[v] ) { // 如果v不在队列中 Q.push( v ); // v入队 inq[v] = true; // 设置v为在队列中 num[v]++; // v的入队次数加1 if( num[v] >= n ) return false; // 有可达负环 } } } } return true; // 无可达负环 } int main() { int n, m; scanf( "%d%d", &n, &m ); int a, b, l; for( int i = 0; i < m; i++ ) { scanf( "%d%d%d", &a, &b, &l ); a--; b--; Edge e; e.v = b; e.l = l; MGraph[a].push_back( e ); } SPFA( 0, n ); for( int i = 1; i < n; i++ ) { printf( "%d ", dist[i] ); } return 0; }