最短路径——Bellman-Ford算法以及SPFA算法

#include<iostream>
#include<queue> 
using namespace std;
const int maxn = 1000;
const int INF = 0x3f3f3f3f;
int u[maxn],v[maxn],w[maxn],dis[maxn],flag;//dis:从起始点到当前点的最短路径    
int n,m,x;//n:顶点数  m:边数  x:起始点  
void Ford(int s){
  for(int i = 1; i <= n; i++){//dis数组进行初始化 
    dis[i] = INF;
  } 
  dis[s] = 0;
  for(int i = 0; i < n-1;i++){//
    flag = 0;//flag:用于标记此次是否所有边是否进行松弛了.
    for(int j = 0; j < m; j++){
      if(dis[v[j]]>=dis[u[j]]+w[j]){
        dis[v[j]] = dis[u[j]]+w[j];
        flag = 1;
      }
    } 
    if(!flag){//如果 这次没有进行松弛,说明所有的点 都已松弛完毕. 
      break;
    }
  } 
}
int main()
{
  cin>>n>>m>>x;
  for(int i = 0; i<m; i++) {
    cin>>u[i]>>v[i]>>w[i];
  }
  Ford(x);
  for(int i = 1; i <= n; i++){
    cout<<dis[i]<<"\t";
  }
  cout<<endl; 
  return 0;
}

#include<iostream>
#include<queue>
using namespace std;
const int maxn = 100;
const int INF = 0x3f3f3f3f;
int n,m,s,c,num;
int head[maxn],dis[maxn],vis[maxn];//vis:标记节点是否在队列中 
struct node{
  int next,to,w;
}e[maxn*maxn]; 
void add(int u,int v,int cc){
  e[++num].next = head[u];
  e[num].to = v;
  e[num].w = cc;
  head[u] = num;
}
void spfa(int u){
  for(int i = 1; i <= n; i++){//dis进行初始化. 
    dis[i] = INF;
  }
  queue<int> q;
  q.push(u);
  vis[u] = 1;
  dis[u] = 0;
  while(!q.empty()){
    int x = q.front();
    q.pop();//怕最后忘记弹出,直接在这里处理吧.. 
    vis[x] = 0;
    for(int i = head[x]; i; i=e[i].next){
      if(dis[e[i].to] > dis[x]+e[i].w){//如果该边可以松弛 
        dis[e[i].to] = dis[x]+e[i].w;//dis更新 
        if(!vis[e[i].to]) {
          q.push(e[i].to);
          vis[e[i].to] = 1;
        }
      } 
    }
  }
} 
int main()
{
  int u,v,w;
  cin>>n>>m>>s;
  for(int i = 0; i < m; i++){
    cin>>u>>v>>w;
    add(u,v,w);
  } 
  spfa(s);
  for(int i = 1; i<=n;i++){
    cout<<dis[i]<<"\t";
  }
  cout<<endl;
  return 0; 
 } 
/*
5 7 1
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6
*/