[关闭]
@Archger 2016-07-10T15:52:16.000000Z 字数 8434 阅读 745

最短路

ACM 最短路 图论

  1. 最短路
  2. Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
  3. Total Submission(s): 28761    Accepted Submission(s): 12444
  6. Problem Description
  7. 在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
  11. Input
  12. 输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
  13. 输入保证至少存在1条商店到赛场的路线。
  16. Output
  17. 对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
  20. Sample Input
  21. 2 1
  22. 1 2 3
  23. 3 3
  24. 1 2 5
  25. 2 3 5
  26. 3 1 2
  27. 0 0
  30. Sample Output
  31. 3
  32. 2

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2544

求最短路，我是看《挑战程序设计竞赛》里的书学的。
里面介绍了三种方法： Bellman-Ford、Dijkstra and Floyd
三者区别也都很明显：

Bellman-Ford：

求单源最短路，可以判断有无负权回路（若有，则不存在最短路）， 时效性较好，时间复杂度O（VE）。

Bellman-Ford算法是求解单源最短路径问题的一种算法。

  单源点的最短路径问题是指： 给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。

  与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。       设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。

Dijkstra：

求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。 源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。 当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2） 。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。

Floyd：

求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。 Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。

Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。

Floyd-Warshall的原理是动态规划： 设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。 若最短路径经过点k，则Di,j,k = Di,k,k-1 + Dk,j,k-1； 若最短路径不经过点k，则Di,j,k = Di,j,k-1。 因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。

在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。 Floyd-Warshall算法的描述如下： for k ← 1 to n do for i ← 1 to n do for j ← 1 to n do if (Di,k + Dk,j < Di,j) then Di,j ← Di,k + Dk,j; 其中Di,j表示由点i到点j的代价，当Di,j为 ∞ 表示两点之间没有任何连接。

后来，我看Bellman-Ford的队列优化，SPFA（Shortest Path Faster Algorithm ）。

SPFA：

是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k<

与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。

SPFA算法可以用于存在负数边权的图，这与dijkstra算法是不同的。

与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。

在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为Bellman-ford算法，其时间复杂度为O(VE)。

SPFA算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的使用堆优化的版本。通常的SPFA算法在一类网格图中的表现不尽如人意。

然后，这道题我用了SPFA，Dijkstra和Floyd来做（Bellman-Ford 太慢，就不做了）
这道题，当时我怎么做，做不出来，后来发现是 MAX 设定为 0x7fffffff 问题。设置成别的大数就没事。
贡献了N个WA啊！！！
郁闷ING。。。

SPFA：

  1. /**************************************** 
  2. ***************************************** 
  3. *        Author:Tree                    * 
  4. *From :http://blog.csdn.net/lttree      * 
  5. * Title : 最短路                       * 
  6. *Source: hdu 2544                       * 
  7. * Hint : SPFA                           * 
  8. ***************************************** 
  9. ****************************************/  
  11. #include <stdio.h>  
  12. #include <queue>  
  13. using namespace std;  
  15. #define RANGE 101  
  16. #define MAX 0x3f3f3f3f  
  17. int cost[RANGE][RANGE];  
  18. int d[RANGE];  
  19. bool used[RANGE];  
  20. int n,m;  
  22. void spfa( int s )  
  23. {  
  24.     int i,now;  
  25.     // 初始化  
  26.     for( i=1;i<=n;++i )  
  27.     {  
  28.         d[i]=MAX;  
  29.         used[i]=false;  
  30.     }  
  32.     d[s]=0;  
  33.     queue <int> q;  
  34.     q.push(s);  
  35.     used[s] = true;  
  37.     while(!q.empty())  
  38.     {  
  39.         now = q.front();  
  40.         q.pop();  
  41.         used[now] = false;  
  42.         for(i = 1; i <= n; i++)  
  43.         {  
  44.             if(d[i] > d[now] + cost[now][i])  
  45.             {  
  46.                 d[i] = d[now] + cost[now][i];  
  47.                 if(used[i] == 0)  
  48.                 {  
  49.                     q.push(i);  
  50.                     used[i] = true;  
  51.                 }  
  52.             }  
  53.         }  
  54.     }  
  55. }  
  57. int main()  
  58. {  
  59.     int i,j,A,B,C;  
  60.     while( scanf("%d%d",&n,&m) )  
  61.     {  
  62.         if( !n && !m )  break;  
  63.         // 初始化  
  64.         for( i=1;i<=n;++i )  
  65.             for( j=1;j<=i;++j )  
  66.                 if( i==j )  cost[i][j]=0;  
  67.                 else    cost[i][j]=cost[j][i]=MAX;  
  69.         for( i=0;i<m;++i )  
  70.         {  
  71.             scanf("%d%d%d",&A,&B,&C);  
  72.             cost[A][B]=cost[B][A]=C;  
  73.         }  
  75.         spfa(1);  
  76.         printf("%d\n",d[n]);  
  77.     }  
  78.     return 0;  
  79. }

Dijkstra：

  1. /**************************************** 
  2. ***************************************** 
  3. *        Author:Tree                    * 
  4. *From :http://blog.csdn.net/lttree      * 
  5. * Title : 最短路                       * 
  6. *Source: hdu 2544                       * 
  7. * Hint : Dijkstra                       * 
  8. ***************************************** 
  9. ****************************************/  
  11. #include <stdio.h>  
  12. #define MAX 0x3f3f3f3f  
  13. #define RANGE 101  
  15. int cost[RANGE][RANGE];  
  16. int d[RANGE];  
  17. bool used[RANGE];  
  19. int n,m;  
  20. int Min( int a,int b )  
  21. {  
  22.     return a<b?a:b;  
  23. }  
  25. void Dijkstra( int s )  
  26. {  
  27.     int i,v,u;  
  28.     for( i=1;i<=n;++i )  
  29.     {  
  30.         used[i]=false;  
  31.         d[i]=cost[1][i];  
  32.     }  
  33.     d[s]=0;  
  35.     while( true )  
  36.     {  
  37.         v=-1;  
  38.         for( u=1;u<=n;++u )  
  39.             if( !used[u] && ( v==-1 || d[u]<d[v]) )  
  40.                 v=u;  
  41.         if( v==-1 ) break;  
  42.         used[v]=true;  
  44.         for( u=1;u<=n;++u )  
  45.             d[u]=Min( d[u],d[v]+cost[v][u] );  
  46.     }  
  47. }  
  49. int main()  
  50. {  
  51.     int A,B,C,i,j;  
  53.     while( scanf("%d%d",&n,&m) )  
  54.     {  
  55.         if( !n && !m )  break;  
  57.         // 初始化  
  58.         for( i=1;i<=n;++i )  
  59.             for( j=1;j<=i;++j )  
  60.                 if( i==j )  cost[i][j]=0;  
  61.                 else    cost[i][j]=cost[j][i]=MAX;  
  63.         for( i=0;i<m;++i )  
  64.         {  
  65.             scanf("%d%d%d",&A,&B,&C);  
  66.             cost[A][B]=cost[B][A]=C;  
  67.         }  
  69.         Dijkstra(1);  
  70.         printf("%d\n",d[n]);  
  71.     }  
  72.     return 0;  
  73. }

Floyd：

  1. /**************************************** 
  2. ***************************************** 
  3. *        Author:Tree                    * 
  4. *From :http://blog.csdn.net/lttree      * 
  5. * Title : 最短路                       * 
  6. *Source: hdu 2544                       * 
  7. * Hint : Floyd                          * 
  8. ***************************************** 
  9. ****************************************/  
  11. #include <stdio.h>  
  12. #define MAX 0x3f3f3f3f  
  13. #define RANGE 105  
  15. int d[RANGE][RANGE];  
  16. int n;  
  18. int Min( int a,int b )  
  19. {  
  20.     return a<b?a:b;  
  21. }  
  22. void warshall_floyd( void )  
  23. {  
  24.     int i,j,k;  
  25.     for( k=1;k<=n;++k )  
  26.         for( i=1;i<=n;++i )  
  27.             for( j=1;j<=n;++j )  
  28.                 d[i][j]=Min( d[i][j],d[i][k]+d[k][j] );  
  29. }  
  31. int main()  
  32. {  
  33.     int m,A,B,C,i,j;  
  35.     while( scanf("%d%d",&n,&m) )  
  36.     {  
  37.         if( !n && !m )  break;  
  39.         // 初始化  
  40.         for( i=1;i<=n;++i )  
  41.             for( j=1;j<=i;++j )  
  42.             {  
  43.                 if( i==j ) d[i][j]=0;  
  44.                 else    d[i][j]=d[j][i]=MAX;  
  45.             }  
  47.         // 输入  
  48.         for( i=0;i<m;++i )  
  49.         {  
  50.             scanf("%d%d%d",&A,&B,&C);  
  51.             d[A][B]=d[B][A]=C;  
  52.         }  
  54.         // floyd算法求最短路  
  55.         warshall_floyd();  
  56.         printf("%d\n",d[1][n]);  
  57.     }  
  58.     return 0;  
  59. }

整体测试代码

  1. #include<iostream>
  2. #include<string>
  3. #include<string.h>
  4. #include<algorithm>
  5. #include<iomanip>
  6. #include<cstdio>
  7. #include<queue>
  8. #include<stack> 
  9. #include<vector>
  10. #include<functional>  
  11. #define INF 99999
  12. using namespace std;
  14. typedef pair<int, int> P;
  16. struct edge {
  17.     int from, to, cost;
  18. };
  20. int n, m;           //n为顶点数，m为边数
  21. int a[100][100];
  23. void warshall()
  24. {
  25.     int b[100][100] = { 0 };
  26.     for (int i = 0; i <= n; i++)
  27.         for (int j = 0; j <= n; j++)
  28.             b[i][j] = a[i][j];
  29.     cout << "Floyd-warshall: \n";
  30.     for (int i = 1; i <= n; i++)
  31.     {
  32.         for (int j = 1; j <= n; j++)
  33.         {
  34.             for (int k = 1; k <= n; k++)
  35.             {
  36.                 if (b[j][k] > b[j][i] + b[i][k])
  37.                 {
  38.                     b[j][k] = b[j][i] + b[i][k];
  39.                 }
  40.             }
  41.         }
  42.     }
  43.     for (int i = 1; i <= n; i++)
  44.     {
  45.         for (int j = 1; j <= n; j++)
  46.         {
  47.             cout << b[i][j] << " ";
  48.         }
  49.         cout << endl;
  50.     }
  51. }
  53. void Dijkstra()
  54. {
  55.     int dis[100] = { 0 };
  56.     bool book[100] = { 0 };
  57.     int b[100][100] = { 0 };
  58.     for (int i = 0; i <= n; i++)
  59.         for (int j = 0; j <= n; j++)
  60.             b[i][j] = a[i][j];
  61.     for (int i = 1; i <= n; i++)
  62.     {
  63.         dis[i] = a[1][i];
  64.     }
  65.     book[1] = 1;
  67.     for (int i = 1; i <= n - 1; i++)
  68.     {
  69.         int minv = INF, min = 0;
  70.         for (int i = 1; i <= n; i++)
  71.         {
  72.             if (!book[i] && minv > dis[i])
  73.             {
  74.                 minv = dis[i];                   //在取最小值的过程中可以用堆优化
  75.                 min = i;
  76.             }
  77.         }
  78.         book[min] = 1;
  79.         for (int j = 1; j <= n; j++)
  80.         {
  81.             if (dis[j] > dis[min] + a[min][j])
  82.             {
  83.                 dis[j] = dis[min] + a[min][j];    //用最短的边对其他所有点进行优化
  84.             }
  85.         }
  86.     }
  87.     for (int i = 1; i <= n; i++)
  88.     {
  89.         cout << dis[i] << " ";
  90.     }
  91.     cout << endl;
  92. }
  94. void Bellman()
  95. {
  96.     int dis[100] = { 0 };
  97.     int b[100][100] = { 0 };
  98.     for (int i = 0; i <= n; i++)
  99.         for (int j = 0; j <= n; j++)
  100.             b[i][j] = a[i][j];
  101.     for (int i = 1; i <= n; i++)
  102.         dis[i] = INF;
  103.     dis[1] = 0;
  104.     /*for (int i = 1; i <= n; i++)
  105.     {
  106.         dis[i] = a[1][i];
  107.     }*/
  108.     for (int i = 1; i <= n - 1; i++)
  109.     {
  110.         for (int j = 1; j <= n; j++)
  111.         {
  112.             for (int k = 1; k <= n; k++)
  113.             {
  114.                 if (dis[k] > dis[j] + a[j][k])
  115.                 {
  116.                     dis[k] = dis[j] + a[j][k];
  117.                 }
  118.             }
  119.         }
  120.     }
  121.     for (int i = 1; i <= n; i++)
  122.     {
  123.         cout << dis[i] << " ";
  124.     }
  125.     cout << endl;
  126. }
  128. void BellmanQueue()
  129. {
  130.     int dis[100] = { 0 };
  131.     int b[100][100] = { 0 };
  132.     for (int i = 0; i <= n; i++)
  133.         for (int j = 0; j <= n; j++)
  134.             b[i][j] = a[i][j];
  135.     for (int i = 1; i <= n; i++)
  136.         dis[i] = INF;
  137.     dis[1] = 0;
  138.     queue<int> que;
  139.     bool book[100] = { 0 };
  140.     que.push(1);
  141.     book[1] = 1;
  142.     while (que.size())
  143.     {
  144.         int k = que.front();
  145.         que.pop();
  146.         for (int i = 1; i <= n; i++)
  147.         {
  148.             if (dis[i] > dis[k] + b[k][i])
  149.             {
  150.                 dis[i] = dis[k] + b[k][i];
  151.                 if (!book[i])
  152.                 {
  153.                     que.push(i);
  154.                     book[i] = 1;
  155.                 }
  156.             }
  157.         }
  158.         book[k] = 0;
  159.     }
  160.     for (int i = 1; i <= n; i++)
  161.     {
  162.         cout << dis[i] << " ";
  163.     }
  164.     cout << endl;
  165. }
  167. void warshall2()
  168. {
  169.     vector<edge> G[100];
  170.     int n, m;
  171.     cin >> n >> m;
  172.     for (int i = 0; i < m; i++)
  173.     {
  174.         int p;
  175.         edge q;
  176.         cin >> p >> q.to >> q.cost;
  177.         G[p].push_back(q);
  178.     }
  179.     for (int i = 1; i <= n; i++)
  180.     {
  181.         for (int k = 1; k <= n; k++)
  182.         {
  183.             for (int j = 0; j < G[k].size(); j++)
  184.             {
  185.                 edge e = G[k][j];
  186.             }
  187.         }
  188.     }
  189.     cout << "不会\n";
  190. }
  192. void Dijkstra2()
  193. {
  194.     vector<edge> G[100];
  195.     int n, m;
  196.     cin >> n >> m;
  197.     int dis[100] = { 0 };
  198.     fill(dis, dis + 100, INF);
  199.     dis[1] = 0;
  200.     for (int i = 0; i < m; i++)
  201.     {
  202.         int p;
  203.         edge q;
  204.         cin >> p >> q.to >> q.cost;
  205.         G[p].push_back(q);
  206.     }
  207.     priority_queue<P, vector<P>, greater<P> >que;
  208.     que.push(P(0, 1));
  209.     while (que.size())
  210.     {
  211.         P p= que.top(); que.pop();
  212.         for (int i = 0; i < G[p.second].size(); i++)
  213.         {
  214.             edge e = G[p.second][i];
  215.             if (dis[e.to] > dis[p.second] + e.cost)
  216.             {
  217.                 dis[e.to] = dis[p.second] + e.cost;
  218.                 que.push(P(dis[e.to], e.to));
  219.             }
  220.         }
  221.     }
  222.     for (int i = 1; i <= n; i++)
  223.     {
  224.         cout << dis[i] << " ";
  225.     }
  226.     cout << endl;
  227. }
  229. void Bellman2()
  230. {
  231.     edge G[100];
  232.     int n, m;
  233.     cin >> n >> m;
  234.     int dis[100] = { 0 };
  235.     fill(dis, dis + 100, INF);
  236.     dis[1] = 0;
  237.     for (int i = 0; i < m; i++)
  238.     {
  239.         cin >> G[i].from >> G[i].to >> G[i].cost;
  240.     }
  241.     for (int i = 1; i <= n - 1; i++)
  242.     {
  243.         for (int j = 0; j < m; j++)
  244.         {
  245.             dis[G[j].to] = min(dis[G[j].to], dis[G[j].from] + G[j].cost);
  246.         }
  247.     }
  248.     for (int i = 1; i <= n; i++)
  249.     {
  250.         cout << dis[i] << " ";
  251.     }
  252.     cout << endl;
  253. }
  255. int main()
  256. {
  257.     cin >> n >> m;
  258.     for(int i=0;i<=n;i++)
  259.         for (int j = 0; j <= n; j++)
  260.         {
  261.             if (i == j) a[i][j] = 0;
  262.             else a[i][j] = INF;
  263.         }
  264.     for (int i = 1; i <= m; i++)
  265.     {
  266.         int p, q, t;
  267.         cin >> p >> q >> t;
  268.         a[p][q] = t;
  269.     }
  270.     cout << "邻接矩阵:\n";
  271.     cout << "1:Floyd-warshall    2:Dijkstra    3:Bellman-Ford    4:Bellman队列优化(SPFA)\n";
  272.     cout << "邻接表\n";
  273.     cout << "5:Floyd-warshall    6:Dijkstra(堆优化)   7：Bellman-Ford\n";
  274.     int t;
  275.     while (cin >> t)
  276.     {
  277.         if (t == 1)
  278.         {
  279.             warshall();
  280.         }
  281.         else if (t == 2)
  282.         {
  283.             cout << "Dijkstra:\n";
  284.             Dijkstra();
  285.         }
  286.         else if (t == 3)
  287.         {
  288.             cout << "Bellman-Ford:\n";
  289.             Bellman();
  290.         }
  291.         else if (t == 4)
  292.         {
  293.             cout << "Bellman队列优化:\n";
  294.             BellmanQueue();
  295.         }
  296.         else if (t == 5)
  297.         {
  298.             cout << "Floyd-warshall（邻接表）:\n";
  299.             warshall2();
  300.         }
  301.         else if (t == 6)
  302.         {
  303.             cout << "Dijkstra(堆优化) \n";
  304.             Dijkstra2();
  305.         }
  306.         else if (t == 7)
  307.         {
  308.             cout << "Bellman-Ford:\n";
  309.             Bellman2();
  310.         }
  311.     }
  312. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注