[关闭]
@lychee123 2017-09-09T23:31:46.000000Z 字数 4605 阅读 1158

power oj-1799: WS旅行社（spfa(求单源最短路，能有负边)）

图论

是一种求单源最短路的算法

算法中需要用到的主要变量

int n;  //表示n个点，从1到n标号
int st,en;  //st为源点，en为终点
int dis[N];  //d[i]表示源点st到点i的最短路
int pre[N];  //记录在最短路上的前驱
queue<int>q;
bool vis[N]; //vis[i]=true表示点i在队列中vis[i]=false表示不在队列中

几乎所有的最短路算法其步骤都可以分为两步

1.初始化
2.松弛操作

初始化： dis数组全部赋值为INF（无穷大）；
        p数组全部赋值为-1，表示没有前驱
        dis[st]=0;表示st到st的最短路是0。将源点入队；
       （在整个算法中有顶点入队了要记得标记vis数组，有顶点出队了记得消除那个标记）

队列+松弛操作

读取队头顶点u，并将队头顶点u出队（记得消除标记）；将与点u相连的所有点v进行松弛操作，如果能更新估计值（即令dis[v]变小），那么就更新，另外，如果点v没有在队列中，那么要将点v入队（记得标记），如果已经在队列中了，那么就不用入队

以此循环，直到队空为止就完成了单源最短路的求解



SPFA可以处理负权边

定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。

证明：

　　每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值dis[v]变小。所以算法的执行会使dis越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着dis值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。

判断有无负环：

　　如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）

例题题面链接

输入
输入的第一行为一个整数T（T组测试数据<=100）
对于每一组测试数据，第一行为两个整数 N,M。N表示地图上的景点个数(N<=2000)。（1 . 2 . 3....N）,M表示道路个数。接下来是M行，每行包括三个整数 S .T .L，表示 景点S与景点T之间的距离是L(L<=1000)
最后一行是两个整数st 和 en ，表示旅行的 起点 和 目的地。

输出
对于每组测试数据，输出包括两行，第一行是从st到en的 最短路径长度。
第二行是输出从起点到目的地所经过的所有景点（如Sample output所示） 以先后顺序输出，数据保证只有一条最优路径
如果不能到达就输出 none!
每组测试数据后输出一个空行。

输入
1
5 8
1 2 1
1 4 10
2 3 5
2 4 1
2 5 12
3 4 1
3 5 1
5 4 8
1 5

输出
Case 1 : 4
1 2 4 3 5

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn=2010;
  4. const int inf=1e9+7;
  5. int t,n,m,u,v,l,st,en,i,j,kk;
  6. int num,p[maxn];//p[id]代表结点id存在的最后一条边的编号，即E[p[id]]]这条边
  7. int dis[maxn],pre[maxn];//dis记录st到i的距离,pre记录i的前驱
  8. bool vis[maxn];//表示i点是否在路径中
  9. struct node
  10. {
  11.     int v,l,next;
  12.     node(){}//默认构造函数，因为下面申明的一个有参构造函数，所以默认构造函数会失效，所以需要再次申明。
  13.     node(int v,int l,int next):v(v),l(l),next(next){}//构造函数
  14. }E[maxn*maxn];
  15. void add(int u,int v,int l)
  16. {
  17.     E[num]=node(v,l,p[u]);//构造函数才能这样赋值
  18.     p[u]=num++;
  19. }
  20. void spfa(int st)
  21. {
  22.     for(i=1;i<=n;i++)
  23.         dis[i]=inf,vis[i]=false;
  24.     pre[st]=-1;//起点没有前驱
  25.     dis[st]=0;//起点到起点的距离为0
  26.     queue<int>q;
  27.     q.push(st);
  28.     vis[st]=true;//起点进入队列
  29.     int now,next;//now为现在的这个点，next为与之相连的点
  30.     while(!q.empty())
  31.     {
  32.         now=q.front();
  33.         q.pop();
  34.         vis[now]=false;//取出了now
  35.         for(i=p[now];i!=-1;i=E[i].next)//反向找与之相连的点，从最后加入的边开始到最开始，直到遍历完所有的与now相连的点
  36.         {
  37.             next=E[i].v;//与之相连的点
  38.             if(dis[next]>dis[now]+E[i].l)//松弛
  39.             {
  40.                 dis[next]=dis[now]+E[i].l;
  41.                 pre[next]=now;
  42.                 if(!vis[next])//当next不在队列里就丢进去，并且标记该点已经在队列里面了
  43.                 {
  44.                     q.push(next);
  45.                     vis[next]=true;
  46.                 }
  47.             }
  48.         }
  49.     }
  50. }
  51. void out(int x)//递归输出（然而还是懵逼的）
  52. {   //commit by w703710691d: 如果这个点不是起点，那就先输出他前驱及其之前的点，最后在输出这个点 
  53.     if(pre[x]==-1)  //这个点已经是起点了，输出的时候注意下格数。
  54.     {
  55.         if(x==en)
  56.             printf("%d\n",en);
  57.         else
  58.             printf("%d ",x);
  59.         return;
  60.     }
  61.     out(pre[x]);    //不是起点，先输出前面的点
  62.     //在输出这个点
  63.     if(x==en)
  64.         printf("%d\n",en);
  65.     else
  66.         printf("%d ",x);
  67. }
  68. int main()
  69. {
  70.     scanf("%d",&t);
  71.     for(kk=1;kk<=t;kk++)
  72.     {
  73.         num=0;
  74.         memset(p,-1,sizeof(p));//一定要记得初始化
  75.         scanf("%d%d",&n,&m);
  76.         for(i=1;i<=m;i++)
  77.         {
  78.             scanf("%d%d%d",&u,&v,&l);
  79.             add(u,v,l);
  80.             add(v,u,l);
  81.         }
  82.         scanf("%d%d",&st,&en);
  83.         spfa(st);
  84.         if(dis[en]==inf)
  85.         {
  86.             printf("Case %d : none!\n",kk);
  87.             puts("");//换行的意思
  88.         }
  89.         else
  90.         {
  91.             printf("Case %d : %d\n",kk,dis[en]);
  92.             //out(en);//递归输出
  93.             stack<int>s;
  94.             for(i=en;pre[i]!=-1;i=pre[i])
  95.             {
  96.                 s.push(i);
  97.             }
  98.             s.push(st);
  99.             while(!s.empty())
  100.             {
  101.                 if(s.top()==st)
  102.                     printf("%d",s.top());
  103.                 else if(s.top()==en)
  104.                     printf(" %d\n",s.top());
  105.                 else
  106.                     printf(" %d",s.top());
  107.                 s.pop();
  108.             }
  109.             puts("");
  110.         }
  111.     }
  112.     return 0;
  113. }

此题的堆优化Dij写法，堆优化的思想就是把Dij暴力找点的过程，用优先队列代替了，整体复杂度位。写法和spfa差不太多，但是比spfa稳定很多。

  1. #include<bits/stdc++.h>
  2. /* 可以考虑使用pb_ds里面的堆，获取更高性能
  3. #include<ext/pb_ds/priority_queue.hpp>
  4. using namespace __gnu_pbds;
  5. */
  6. using namespace std;
  7. const int maxn = 2e3 + 5;
  8. const int maxm = maxn * maxn;   ///边要开多少，自己掂量吧
  9. struct EDGE
  10. {
  11.     int to, next, len;
  12.     EDGE() {}
  13.     EDGE(int to, int next, int len): to(to), next(next), len(len) {}
  14. } edge[maxm];
  15. int head[maxn], edgecnt;
  16. void init()
  17. {
  18.     memset(head, -1, sizeof(head));
  19.     edgecnt = 0;
  20. }
  21. void add(int s, int t, int l)
  22. {
  23.     edge[edgecnt] = EDGE(t, head[s], l);
  24.     head[s] = edgecnt++;
  25. }
  26. int pre[maxn], dis[maxn], vis[maxn];    ///分别位最短路上的前驱，到起点的距离，是否已经在最短路上
  27. struct HeapNode ///优先队列中的元素，由于是大者有限，反着重载之后dis小的先出来
  28. {
  29.     int u, dis;
  30.     HeapNode(int u, int dis): u(u), dis(dis) {}
  31.     bool operator < (const HeapNode &b) const
  32.     {
  33.         return dis > b.dis;
  34.     }
  35. };
  36. void HeapDij(int st)    ///堆优化Dij,以st位起点
  37. {
  38.     memset(vis, 0, sizeof(vis));
  39.     memset(dis, 0x7F, sizeof(dis));
  40.     memset(pre, -1, sizeof(pre));
  41.     priority_queue<HeapNode> q;
  42.     /* pb_ds的堆就应该这样定义了
  43.     __gnu_pbds::priority_queue<HeapNode> q;
  44.     */
  45.     dis[st]  = 0;
  46.     q.emplace(st, 0);
  47.     /* pb_ds的东西暂时不支持emplace
  48.     q.push(HeapNode(st, 0));
  49.     */
  50.     while(!q.empty())
  51.     {
  52.         int u = q.top().u;
  53.         q.pop();
  54.         if(vis[u])  ///标记，一个点只会更新周围的点一次
  55.             continue;
  56.         vis[u] = 1; 
  57.         for(int i = head[u]; ~i; i = edge[i].next)
  58.         {
  59.             int v = edge[i].to;
  60.             if(dis[v] > dis[u] + edge[i].len)
  61.             {
  62.                 pre[v] = u; ///记录前驱
  63.                 dis[v] = dis[u] + edge[i].len;
  64.                 q.emplace(v, dis[v]);
  65.                 /* pb_ds的东西暂时不支持emplace
  66.                 q.push(HeapNode(v, dis[v]));
  67.                 */
  68.             }
  69.         }
  70.     }
  71. }
  72. int main()
  73. {
  74.     int T, ks = 0;
  75.     scanf("%d", &T);
  76.     while(T--)
  77.     {
  78.         init();
  79.         int n, m;
  80.         scanf("%d %d", &n, &m);
  81.         while(m--)
  82.         {
  83.             int s, t, l;
  84.             scanf("%d %d %d", &s, &t, &l);
  85.             add(s, t, l);
  86.             add(t, s, l);
  87.         }
  88.         int st, en;
  89.         scanf("%d %d", &st, &en);
  90.         HeapDij(st);
  91.         printf("Case %d : ", ++ks);
  92.         if(!vis[en])    ///简单的判断，没被标记，肯定连图都不连通
  93.             puts("none!");
  94.         else
  95.         {
  96.             printf("%d\n", dis[en]);
  97.             vector<int> vec;
  98.             while(en != -1) ///沿着pre从终点往起点走
  99.             {
  100.                 vec.push_back(en);
  101.                 en = pre[en];
  102.             }
  103.             for(int i = vec.size() - 1; i >= 0; i--)
  104.             {
  105.                 printf("%d", vec[i]);
  106.                 if(i)
  107.                     printf(" ");
  108.                 else
  109.                     printf("\n");
  110.             }
  111.         }
  112.         printf("\n");
  113.     }
  114.     return 0;
  115. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注