最短路

淡淡的烟草味﹌ 2022-06-09 04:28 258阅读 0赞

一下模板均已通过HDUOJ 2544

程序设计竞赛队空间和时间复杂度要求都很高，所以朴素的Dijkstra[算法][Link 1]无论时间还是空间，效率都很低。

所以，一般而言，不带负权的用邻接表建图+堆优化的Dijkstra算法

带负权的的用邻接表建图+SFPA算法

此外，最短路还可以用BFS求，例如边权值都为1的话，就可以用普通队列+BFS求得，边权值不为1，可以用优先队列+BFS求得，这里就不给出实现代码了

1.最短路模板题+邻接矩阵建图+朴素算法，复杂度O(V^2)

转载自：http://blog.csdn.net/u013615904/article/details/44587775

**\[cpp\]** [view plain][] [copy][view plain]

1.  \#include<iostream>
2.  \#include<vector>
3.  **using****namespace** std; 
4.  **const****int** maxn=105,inf=1<<29; 
5.  **int** n,m,s; 
6.  **int** vis\[maxn\],d\[maxn\],Map\[maxn\]\[maxn\]; 
7.  **void** Dijkstra() 
8.  \{ 
9.   fill(vis,vis+maxn,0); 
10.  fill(d,d+maxn,inf); 
11.  d\[s\]=0; 
12. **while**(1) 
13.  \{ 
14. **int** v=-1; 
15. **for**(**int** i=1;i<=n;i++) 
16. **if**(!vis\[i\]&&(v==-1||d\[v\]>d\[i\])) v=i; 
17. **if**(v==-1) **break**; 
18.  vis\[v\]=1; 
19. **for**(**int** i=1;i<=n;i++) d\[i\]=min(d\[i\],d\[v\]+Map\[v\]\[i\]); 
20.  \} 
21. \} 
22. **int** main() 
23. \{ 
24. **while**(cin>>n>>m,(n+m)) 
25.  \{ 
26.  fill(&Map\[0\]\[0\],&Map\[maxn\]\[0\],inf); 
27. **for**(**int** i=0;i<m;i++) 
28.  \{ 
29. **int** a,b,w; 
30.  cin>>a>>b>>w; 
31.  Map\[a\]\[b\]=Map\[b\]\[a\]=min(Map\[a\]\[b\],w); 
32.  \} 
33.  s=1; 
34.  Dijkstra(); 
35.  cout<<d\[n\]<<endl; 
36.  \} 
37. **return** 0; 
38. \}

2.最短路模板+邻接表建图+堆优化(优先队列) 复杂度O(E\*log(E))

**\[cpp\]** [view plain][] [copy][view plain]

1.  \#include<iostream>
2.  \#include<queue>
3.  \#include<vector>
4.  \#include<cstdio>
5.  **using****namespace** std; 
6.  **const****int** maxn=105,inf=1<<29; 
7.  **struct** edge\{ **int** to,cost;\}; 
8.  **struct** node 
9.  \{ 
10. **int** len,v; 
11. **friend****bool** operator <(node x,node y) 
12.  \{ 
13. **return** x.len>y.len; 
14.  \} 
15. \}; 
16. **int** d\[maxn\]; 
17. **int** n,m,s; 
18. vector<edge>G\[maxn\]; 
19. **void** Dijkstra() 
20. \{ 
21.  priority\_queue<node>q; 
22.  fill(d,d+maxn,inf);d\[s\]=0; 
23.  node t; 
24.  t.len=0;t.v=s; 
25.  q.push(t); 
26. **while**(q.size()) 
27.  \{ 
28.  t=q.top();q.pop(); 
29. **if**(d\[t.v\]<t.len) **continue**; 
30. **for**(**int** i=0;i<G\[t.v\].size();i++) 
31.  \{ 
32.  edge e=G\[t.v\]\[i\]; 
33. **if**(d\[e.to\]>d\[t.v\]+e.cost) 
34.  \{ 
35.  d\[e.to\]=d\[t.v\]+e.cost; 
36.  node temp=\{d\[e.to\],e.to\}; 
37.  q.push(temp); 
38.  \} 
39.  \} 
40.  \} 
41. \} 
42. **int** main() 
43. \{ 
44. //while(cin>>n>>m&&(n+m))
45. **while**(~scanf("%d%d",&n,&m),(n+m)) 
46.  \{ 
47. **for**(**int** i=0;i<=n;i++) G\[i\].clear(); 
48. **for**(**int** i=0;i<m;i++) 
49.  \{ 
50. **int** a,b,w; 
51.  edge t,rt; 
52.  scanf("%d%d%d",&a,&b,&w); 
53. //cin>>a>>b>>w;
54.  t.to=b;t.cost=w; 
55.  rt.to=a;rt.cost=w; 
56.  G\[a\].push\_back(t); 
57.  G\[b\].push\_back(rt); 
58.  \} 
59.  s=1; 
60.  Dijkstra(); 
61.  cout<<d\[n\]<<endl; 
62.  \} 
63. **return** 0; 
64. \}

3.最短路模板+邻接表建图+SFPA

**\[cpp\]** [view plain][] [copy][view plain]

1.  \#include<iostream>
2.  \#include<queue>
3.  \#include<vector>
4.  \#include<cstdio>
5.  **using****namespace** std; 
6.  **const****int** maxn=105,inf=1<<29; 
7.  **struct** edge\{ **int** to,cost;\}; 
8.  **int** d\[maxn\],vis\[maxn\]; 
9.  **int** n,m,s; 
10. vector<edge>G\[maxn\]; 
11. **void** SFPA() 
12. \{ 
13.  fill(d,d+maxn,inf);d\[s\]=0; 
14.  fill(vis,vis+maxn,0); 
15.  queue<**int**> q; 
16.  q.push(s); 
17. **while**(!q.empty()) 
18.  \{ 
19. **int** u=q.front(); 
20.  q.pop(); 
21.  vis\[u\]=0; 
22. **for**(**int** i=0;i<G\[u\].size();i++) 
23.  \{ 
24. **int** v=G\[u\]\[i\].to,len=G\[u\]\[i\].cost; 
25. **if**(d\[v\]>d\[u\]+len) 
26.  \{ 
27.  d\[v\]=d\[u\]+len; 
28. **if**(vis\[v\]==0) 
29.  \{ 
30.  vis\[v\]=1; 
31.  q.push(v); 
32.  \} 
33.  \} 
34.  \} 
35.  \} 
36. \} 
37. **int** main() 
38. \{ 
39. //while(cin>>n>>m&&(n+m))
40. **while**(~scanf("%d%d",&n,&m),(n+m)) 
41.  \{ 
42. **for**(**int** i=0;i<=n;i++) G\[i\].clear(); 
43. **for**(**int** i=0;i<m;i++) 
44.  \{ 
45. **int** a,b,w; 
46.  edge t,rt; 
47.  scanf("%d%d%d",&a,&b,&w); 
48. //cin>>a>>b>>w;
49.  t.to=b;t.cost=w; 
50.  rt.to=a;rt.cost=w; 
51.  G\[a\].push\_back(t); 
52.  G\[b\].push\_back(rt); 
53.  \} 
54.  s=1; 
55.  SFPA(); 
56.  cout<<d\[n\]<<endl; 
57.  \} 
58. **return** 0; 
59. \}

4.最短路模板+floyd

**\[cpp\]** [view plain][] [copy][view plain]

1.  \#include<iostream>
2.  **using****namespace** std; 
3.  **const****int** maxn=105,inf=1<<29; 
4.  **int** n,m; 
5.  **int** Map\[maxn\]\[maxn\]; 
6.  **void** floyd() 
7.  \{ 
8.  **for**(**int** k=1;k<=n;k++) 
9.  **for**(**int** i=1;i<=n;i++) 
10. **for**(**int** j=1;j<=n;j++) 
11.  Map\[i\]\[j\]=min(Map\[i\]\[j\],Map\[i\]\[k\]+Map\[k\]\[j\]); 
12. \} 
13. **int** main() 
14. \{ 
15. **while**(cin>>n>>m,(n+m)) 
16.  \{ 
17.  fill(&Map\[0\]\[0\],&Map\[maxn\]\[0\],inf); 
18. **for**(**int** i=0;i<m;i++) 
19.  \{ 
20. **int** a,b,w; 
21.  cin>>a>>b>>w; 
22.  Map\[a\]\[b\]=Map\[b\]\[a\]=min(Map\[a\]\[b\],w); 
23.  \} 
24.  floyd(); 
25.  cout<<Map\[1\]\[n\]<<endl; 
26.  \} 
27. **return** 0; 
28. \}

记录路径的最短路，floyd算法实现，以HDU 1385为例

**\[cpp\]** [view plain][] [copy][view plain]

1.  <pre name="code"**class**="cpp">\#include<iostream> 
2.  \#include<cstdio>
3.  **using****namespace** std; 
4.  **const****int** maxn=105,inf=1<<29; 
5.  **int** n,m; 
6.  **int** Map\[maxn\]\[maxn\],p\[maxn\]\[maxn\],tax\[maxn\]; 
7.  **void** floyd() 
8.  \{ 
9.  **for**(**int** k=1;k<=n;k++) 
10. **for**(**int** i=1;i<=n;i++) 
11. **for**(**int** j=1;j<=n;j++) 
12. //if(Map\[i\]\[j\]>=Map\[i\]\[k\]+Map\[k\]\[j\]+tax\[k\]) Map\[i\]\[j\]=Map\[i\]\[k\]+Map\[k\]\[j\]+tax\[k\],p\[i\]\[j\]=min(p\[i\]\[j\],p\[i\]\[k\]);
13.  \{ 
14. **int** temp=Map\[i\]\[k\]+Map\[k\]\[j\]+tax\[k\]; 
15. **if**(Map\[i\]\[j\]>temp) 
16.  \{ 
17.  Map\[i\]\[j\]=temp; 
18.  p\[i\]\[j\]=p\[i\]\[k\]; 
19.  \} 
20. **else****if**(Map\[i\]\[j\]==temp&&p\[i\]\[j\]>p\[i\]\[k\]) p\[i\]\[j\]=p\[i\]\[k\]; 
21.  \} 
22. \} 
23. **int** main() 
24. \{ 
25. **while**(~scanf("%d",&n),n) 
26.  \{ 
27. **for**(**int** i=1;i<=n;i++) 
28. **for**(**int** j=1;j<=n;j++) 
29.  \{ 
30.  scanf("%d",&Map\[i\]\[j\]); 
31. **if**(Map\[i\]\[j\]==-1) Map\[i\]\[j\]=inf; 
32.  p\[i\]\[j\]=j; 
33.  \} 
34. **for**(**int** i=1;i<=n;i++) scanf("%d",&tax\[i\]); 
35.  floyd(); 
36. **int** s,e; 
37. **while**(scanf("%d%d",&s,&e)&&(s+e)!=-2) 
38.  \{ 
39.  printf("From %d to %d :\\n",s,e); 
40.  printf("Path: "); 
41. **int** u = s; 
42.  printf("%d",u); 
43. **while**(u!=e) 
44.  \{ 
45.  printf("-->%d",p\[u\]\[e\]); 
46.  u= p\[u\]\[e\]; 
47.  \} 
48.  printf("\\nTotal cost : %d\\n\\n", Map\[s\]\[e\]); 
49.  \} 
50.  \} 
51. **return** 0; 
52. \} 
53.

[Link 1]: http://lib.csdn.net/base/datastructure
[view plain]: http://blog.csdn.net/u013615904/article/details/44587775#