bellman-ford：
1 #include<iostream> 2 #include<stdio.h> 3 #include<string> 4 #include<algorithm> 5 #include<cmath> 6 #include<vector> 7 using namespace std; 8 #define INF 0x3f3f3f3f 9 #define ll long long 10 struct poi{ 11 int from,to,cost; 12 }; 13 int dit[20007]; 14 int main() 15 { 16 int n,m,a; 17 poi s; 18 cin>>n>>m; 19 for(int i=0;i<=20005;i++){ 20 dit[i]=INF; 21 } 22 dit[1]=0; 23 vector<poi> vec[20007]; 24 for(int i=0;i<m;i++){ 25 scanf("%d%d%d",&s.from,&s.to,&s.cost); 26 vec[s.from].push_back(s); 27 } 28 for(int i=1;i<=n-1;i++){//当dit值被改变之后，无法确定是否之后的也会改变，所以进行n-1次 29 for(int j=1;j<=n;j++){//从点j向它的后继节点尝试更新 30 for(int k=0;k<vec[j].size();k++){ 31 if(vec[j][k].cost+dit[j]<dit[vec[j][k].to]){ 32 dit[vec[j][k].to]=vec[j][k].cost+dit[j]; 33 } 34 } 35 } 36 } 37 for(int i=1;i<=n-1;i++){//检验是否出现负权值，出现证明会出现无限小 38 for(int j=1;j<=n;j++){ 39 for(int k=0;k<vec[j].size();k++){ 40 if(vec[j][k].cost+dit[j]<dit[vec[j][k].to]){ 41 dit[vec[j][k].to]=-INF; 42 } 43 } 44 } 45 } 46 for(int i=2;i<=n;i++){ 47 cout<<dit[i]<<endl; 48 } 49 }
SPFA:
用dis数组记录源点到有向图上任意一点距离，其中源点到自身距离为0，到其他点距离为INF。将源点入队，并重复以下步骤：
- 队首x出队
- 遍历所有以队首为起点的有向边(x,i)，若dis[x]+w(x,i)<dis[i]，则更新dis[i]，更新后如果点i不在队列中，则i入队
- 若队列为空，跳出循环；否则继续循环执行操作
如果图是随机生成的，时间复杂度为 O(KM) （K可以认为是个常数，m为边数，n为点数）
但是实际上SPFA的算法复杂度是 O(NM) ，可以构造出卡SPFA的数据，让SPFA超时
所以当权值有负权值时才使用spfa，当权值为正时，请使用dij，至于。。。BF请忘掉他，没用。哪怕SPFA被卡数据也只是变成了BF
1 #include<iostream> 2 #include<cstdio> 3 #include<vector> 4 #include<queue> 5 #include<cstring> 6 #define ll long long 7 using namespace std; 8 int dis[1000000]; 9 int vis[1000000]; 10 int n,m; 11 struct poi{ 12 int a,b,c; 13 }; 14 queue<int>r; 15 vector<poi>vec[20007]; 16 void spfa() 17 { 18 r.push(1); 19 vis[1]=1; 20 int a,b; 21 while(!r.empty()){ 22 a=r.front(); 23 vis[a]=0; 24 r.pop(); 25 for(int i=0;i<vec[a].size();i++){ 26 int k=vec[a][i].b; 27 if(dis[a]+vec[a][i].c<dis[k]){ 28 dis[k]=dis[a]+vec[a][i].c; 29 if(vis[k]==0){ 30 r.push(k); 31 vis[k]=1; 32 } 33 } 34 } 35 } 36 } 37 int main() 38 { 39 cin>>n>>m; 40 poi s; 41 for(int i=0;i<m;i++){ 42 scanf("%d%d%d",&s.a,&s.b,&s.c); 43 vec[s.a].push_back(s); 44 } 45 memset(dis,0x3f,sizeof(dis)); 46 dis[1]=0; 47 spfa(); 48 for(int i=2;i<=n;i++){ 49 cout<<dis[i]<<endl; 50 } 51 }