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

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. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注