最短路径问题---Floyed（弗洛伊德算法），dijkstra算法，SPFA算法

在NOIP比赛中，如果出图论题最短路径应该是个常考点。

求解最短路径常用的算法有：Floyed算法（O(n^3)的暴力算法，在比赛中大概能过三十分）

                                              dijkstra算法 （堆优化之后是O(MlogE),再加些玄学优化一般就是正解了，100分做法）

                                          SPFA算法  （ 个人是不建议学习的，在NOIP提高组中出题人是故卡SPFA,它的复杂度是不确定的，它是基于ballman-Fold算法（O(N*E)）的队列优化版）

这个应该都是比较简单的，直接上代码吧

dijkstra

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define MAXN 500010
using namespace std;
int cnt,n,m,s;
int head[MAXN];
int d[MAXN];


struct Edge{
    int s,t,w,next;
}edge[500010];

void add(int u,int v,int wi){
    cnt++;
    edge[cnt].s=u;
    edge[cnt].t=v;
    edge[cnt].w=wi;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

struct HeapNode{
    int pos,dis;
    bool operator < ( const HeapNode &a )const {
       return a.dis<dis;
    }
};

void dijkstra(){
     priority_queue <HeapNode> Q;
     for(int i=1;i<=n;i++) d[i]=2147483647;
     d[s]=0;
     Q.push((HeapNode){s,0});
     while(!Q.empty()){
         while(Q.size() > 1 && Q.top().dis != d[Q.top().pos]) Q.pop();
         HeapNode tmp=Q.top();
         Q.pop();
         int u=tmp.pos;
         for(int i=head[u];i;i=edge[i].next){
             int v=edge[i].t;
             int wi=edge[i].w;
             if(d[v]>d[u]+wi){
                 d[v]=d[u]+wi,
                 Q.push((HeapNode) {v,d[v]});
             }
         }
     }

}

int main(){

  scanf("%d%d%d",&n,&m,&s);
   for(int i=1;i<=m;i++){
       int x,y,z;
  
        scanf("%d%d%d",&x,&y,&z);
       add(x,y,z);
   }
   dijkstra();
   for(int i=1;i<=n;i++){
       printf("%d ",d[i]);
   }

    return 0;
}

SPFA

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue> 
using namespace std;
const int MAXN=10010;
int cnt,n,m,s;
int head[MAXN];
int d[MAXN];
int b[MAXN];
struct Edge{
    int s,t,w,next;
}edge[500010];

void add(int u,int v,int wi){
    cnt++;
    edge[cnt].s=u;
    edge[cnt].t=v;
    edge[cnt].w=wi;
    edge[cnt].next=head[u];
    head[u]=cnt;

}

void spfa(){
    queue<int>q;
    for(int i=1;i<=n;i++){
        d[i]=2147483647;
        b[i]=0;
    }
    q.push(s);d[s]=0;b[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        b[u]=0;
        for(int i=head[u];i;i=edge[i].next){
              int v=edge[i].t;
              if(d[v]>d[u]+edge[i].w){
                  d[v]=d[u]+edge[i].w;
                  if(b[v]==0){
                      b[v]=1;
                      q.push(v);
                  }
             }            
         }
     }
 }
int main(){
  
   scanf("%d%d%d",&n,&m,&s);
   for(int i=1;i<=m;i++){
       int x,y,z;
       scanf("%d%d%d",&x,&y,&z);
       add(x,y,z);
   }
       spfa();
       for(int i=1;i<=n;i++){
           printf("%d ",d[i]);
       }
       return 0;
  }