SPFA：

Warning：SPFA在OI竞赛中慎用，极易容易被卡！！！

基本流程：

从起点开始，每次将扫到的点入队，每个点遍历所有与其相连的点，并更新最短路，如果该点未入队，则将其入队；

均摊复杂度为$ O(KE) $（K=2），但因为SPFA在网格图中入队次数过多，导致卡成原始的Bellman-Ford（$ o(VE) $），所以竞赛中不常用到（但还是要学会的）；

丑陋的代码（洛谷P3371）：

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int n,m,x,y,z,tot,f[],q[],h,t,s,first[],nxt[],last[],en[],len[];

 //f为记录最短路径的数组，q为队列；

 //first，nxt，last，en，len为平平无奇的邻接表；

 bool b[];

 //判断是否在队列中

 void add(int x,int y,int z)

 {

     ++tot;

     if(first[x]==) first[x]=tot; else nxt[last[x]]=tot;

     en[tot]=y;

     len[tot]=z;

     last[x]=tot;

 }

 void SPFA(int x)

 {

     int k=first[x];

     do

     {

         if((long long)len[k]+f[x]<f[en[k]])

         {

             f[en[k]]=len[k]+f[x];

             if(not b[en[k]])

             {

                 ++t;

                 q[t]=en[k];

                 b[en[k]]=true;

             }

         }

         k=nxt[k];

     }

     while(k!=);

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&s);

     for(int i=;i<=m;++i)

     {

         scanf("%d%d%d",&x,&y,&z);

         add(x,y,z);

     }

     for(int i=;i<=n;++i)

     f[i]=;

     f[s]=;

     h=;

     t=;

     SPFA(s);

     while(h<=t)

     {

         SPFA(q[h]);

         b[q[h]]=false;

         ++h;

     }

     for(int i=;i<=n;++i)

         printf("%d ",f[i]);

     return ;

 }

Dijkstra：

最常用的最短路算法（蒟蒻的我最近才学会太菜了）；

基本流程：

定义两个点的集合，S为已求出最短路的点集，T为未求出最短路的点集；

每次在T集合中找到一个Dis值最小的点，将其放入S集合中，并用它更新其他点的最短路；

由此，朴素的Dijkstra在每次选择操作中暴力枚举每个点复杂度为$ O(V) $，更新时的复杂度也为$ O(V) $，及时间复杂度为$ O(V^2) $；

聪（AK）明（IOI）的读者可能已经发现了，选择Dis值最小的点时，暴力枚举过于浪费，为了避免超时，我们可以用堆（或者线段树）优化为$ o(Vlog(E)) $；

每次选择时，直接访问堆的根节点，将其弹出，并把更新的节点压入堆中；（每次压入堆中不必要判是否已入堆，只需要开个bool数组记录该点是否已有最短路即可）

（甚至可以用斐波那契堆优化为$ o(E+Vlog(V)) $）

附上丑陋的代码（CodeChef CLIQUED）：

 #include<cstdio>

 #include<queue>

 #include<iostream>

 using namespace std;

 const int MAXN=;

 const long long INF=1e15+;

 struct node

 {

     int pos;

     long long dis;

     bool operator <(const node &x)const

     {

         return x.dis<dis;

     }

 };

 priority_queue<node> q;

 int tot,first[MAXN],nxt[MAXN],last[MAXN],to[MAXN],len[MAXN];

 //平平无奇的邻接表

 int T,n,k,x,m,s;

 long long dis[MAXN];

 //dis为到每个点的最短路径

 bool vis[MAXN];

 //vis记录每个点是否已有最短路的值

 void dijistra()

 {

     dis[s]=;

     q.push((node){s,});

     while(!q.empty())

     {

         node t=q.top();

         int po=t.pos;

         long long di=t.dis;

         q.pop();

         //取堆的根节点

         if(vis[po])

             continue;

         //如果已有最短路，说明该点已更新过，无需更新

         vis[po]=;

         for(int i=first[po];i;i=nxt[i])

         if(di+len[i]<dis[to[i]])

         {

             dis[to[i]]=di+len[i];

             q.push((node){to[i],di+len[i]});

         }

         //常规松弛(更新最短路径)

     }

 }

 void add(int x,int y,int z)

 {

     tot++;

     if(first[x]==)

         first[x]=tot;

     else

         nxt[last[x]]=tot;

     last[x]=tot;

     to[tot]=y;

     len[tot]=z;

 }

 int main()

 {

     scanf("%d",&T);

     for(int ii=;ii<=T;++ii)

     {

         scanf("%d%d%d%d%d",&n,&k,&x,&m,&s);

         n++;

         for(int i=;i<=n;++i)

             first[i]=;

         for(int i=;i<=m;++i)

         {

             int x,y,z;

             scanf("%d%d%d",&x,&y,&z);

             add(x,y,z);

             add(y,x,z);

         }

         for(int i=;i<=k;++i)

         {

             add(i,n,x);

             add(n,i,);

         }

         for(int i=;i<=n;++i)

             dis[i]=INF;

         for(int i=;i<=n;++i)

             vis[i]=;

         dijistra();

         for(int i=;i<n;++i)

             printf("%lld ",dis[i]);

         printf("\n");

     }

     return ;

 }

巴特西

最短路（模板）【CodeChef CLIQUED，洛谷P3371】

SPFA：

基本流程：

Dijkstra：

基本流程：

最新文章

热门文章