最短路径算法复习：
Dijkstra算法
详细介绍
Dijkstra复杂度是O(N^2)，如果用binary heap优化可以达到O((E+N)logN)，用fibonacci heap可以优化到O(NlogN+E)
其基本思想是采用贪心法，对于每个节点v[i]，维护估计最短路长度最大值，每次取出一个使得该估计值最小的t，并采用与t相连的边对其余点的估计值进行更新，更新后不再考虑t。
在此过程中，估计值单调递减，所以可以得到确切的最短路。
Floyd-Warshall算法
详细介绍
Floyd是计算每对点间最短路径（APSP)的经典算法。
时间复杂度是雷打不动的O(n^3)
*Floyd-Warshall算法的基本思想：
它的基本思想就是动态规划。假设在一个图中有一条从结点A经过B、C、D到达E的路径是最短的，那么从A到B、C、D的路径也分别是最短的。用反证法证明，假如A到D的路径不是最短的，那么加上D到E的路径长度必然比原来的所谓最短长度小，与假设矛盾。
假设k点是结点i到j的路径的一个中间结点，如果路径ik和路径kj都是最短路径，那么ik+kj组成的路径ij必然是最短路径。
通过上面的观察，我们可以推出判断两点(设为i、j)之间的最短路径其实是求出
ij直接相连的距离、i通过其他结点k到达j的距离(即ik + kj)的最小值。
Bellman-Ford算法
详细介绍
Bellman-Ford主要是用于负权图。Bellman-Ford算法即标号修正算法。
实践中常用到的方法通常是FIFO标号修正算法和一般标号修正算法的Dequeue实现。
前者最坏时间复杂度是O(nm), 是解决任意边权的单源最短路经问题的最优强多项式算法。
也可以用这个算法判断是否存在负权回路.
迭代算法的思想：不停地调整图中的顶点值（源点到该点的最短路径值），直到没有点的值调整了为止。
Input:
6 1
0 50 10 0 45 0
0 0 15 0 10 0
20 0 0 15 0 0
0 20 0 0 35 0
0 0 0 30 0 0
0 0 0 3 0 0
1 4
Output:
25
1->3->4
Dijkstra：
1 /*
2 * Problem: 最短路
3 * Author: Xu Fei
4 * Time: 2010.8.1 15:30
5 * Memo: Dijkstra
6 */
7
8 #include<iostream>
9 #include<cstdio>
10 using namespace std;
11
12 const int INF=0xFFFFFFF;
13
14 int N,M;
15 int S[100];
16 int T[100];
17 int pre[100];
18 int dis[100];
19 int cost[100][100];
20 bool vis[100];
21
22 void init()
23 {
24 int i,j;
25
26 scanf("%d%d",&N,&M);
27 for(i=1;i<=N;++i)
28 for(j=1;j<=N;++j)
29 {
30 scanf("%d",&cost[i][j]);
31 if(cost[i][j]==0)
32 cost[i][j]=INF;
33 }
34 for(i=1;i<=M;++i)
35 scanf("%d%d",&S[i],&T[i]);
36 }
37 int dijkstra(int s,int t)
38 {
39 int i,j,Min,kj;
40
41 for(i=1;i<=N;++i)
42 {
43 dis[i]=cost[s][i];
44 vis[i]=true;
45 pre[i]=s;
46 }
47 dis[s]=0; vis[s]=false;
48 for(i=1;i<N;++i)
49 {
50 Min=INF;
51 for(j=1;j<=N;++j)
52 if(vis[j]&&dis[j]<Min)
53 Min=dis[j],kj=j;
54 if(kj==t) break;
55 vis[kj]=false;
56 for(j=1;j<=N;++j)
57 if(vis[j]&&dis[j]>dis[kj]+cost[kj][j])
58 {
59 dis[j]=dis[kj]+cost[kj][j];
60 pre[j]=kj;
61 }
62 }
63 return dis[t];
64 }
65 void dfs(int s,int t)
66 {
67 if(s==t)
68 printf("%d",s);
69 else
70 {
71 dfs(s,pre[t]);
72 printf("->%d",t);
73 }
74 }
75 void solve()
76 {
77 int i;
78
79 for(i=1;i<=M;++i)
80 {
81 printf("%d\n",dijkstra(S[i],T[i]));
82 dfs(S[i],T[i]);
83 printf("\n");
84 }
85 }
86 int main()
87 {
88 freopen("zui.in","r",stdin);
89 freopen("zui.out","w",stdout);
90
91 init();
92 solve();
93 return 0;
94 }
95
Floyd:
1 /*
2 * Problem: 最短路
3 * Author: Xu Fei
4 * Time: 2010.8.1 16.12
5 * Method: Floyd
6 */
7
8 #include<iostream>
9 #include<cstdio>
10 using namespace std;
11
12 const int INF=0xFFFFFFF;
13
14 int N,M;
15 int S[100];
16 int T[100];
17 int mid[100][100];
18 int cost[100][100];
19
20 void init()
21 {
22 int i,j;
23
24 scanf("%d%d",&N,&M);
25 for(i=1;i<=N;++i)
26 for(j=1;j<=N;++j)
27 {
28 scanf("%d",&cost[i][j]);
29 if(i!=j&&cost[i][j]==0)
30 cost[i][j]=INF;
31 mid[i][j]=0;
32 }
33 for(i=1;i<=M;++i)
34 scanf("%d%d",S+i,T+i);
35 }
36 void floyd()
37 {
38 int i,j,k;
39
40 for(k=1;k<=N;++k)
41 for(i=1;i<=N;++i)
42 if(i!=k)
43 for(j=1;j<=N;++j)
44 if(j!=k&&j!=i)
45 if(cost[i][j]>cost[i][k]+cost[k][j])
46 {
47 cost[i][j]=cost[i][k]+cost[k][j];
48 mid[i][j]=k;
49 }
50 }
51 void dfs(int s,int t)
52 {
53 if(mid[s][t]==0) return;
54 dfs(s,mid[s][t]);
55 printf("->%d",mid[s][t]);
56 dfs(mid[s][t],t);
57 }
58 void solve()
59 {
60 int i;
61
62 floyd();
63 for(i=1;i<=M;++i)
64 {
65 printf("%d\n",cost[S[i]][T[i]]);
66 printf("%d",S[i]);
67 dfs(S[i],T[i]);
68 printf("->%d\n",T[i]);
69 }
70 }
71 int main()
72 {
73 freopen("zui.in","r",stdin);
74 freopen("zui.out","w",stdout);
75
76 init();
77 solve();
78 return 0;
79 }
Ford：
1 /*
2 * Problem: 最短路
3 * Author: Xu Fei
4 * Time: 2010.8.1 16.46
5 * Method: Ford
6 */
7
8 #include<iostream>
9 #include<cstdio>
10 using namespace std;
11
12 const int INF=0xFFFFFFF;
13
14 int N,M;
15 bool flag;
16 int S[100];
17 int T[100];
18 int dis[100];
19 int pre[100];
20 int cost[100][100];
21
22 void init()
23 {
24 int i,j;
25
26 scanf("%d%d",&N,&M);
27 for(i=1;i<=N;++i)
28 for(j=1;j<=N;++j)
29 {
30 scanf("%d",&cost[i][j]);
31 if(i!=j&&cost[i][j]==0)
32 cost[i][j]=INF;
33 }
34 for(i=1;i<=M;++i)
35 scanf("%d%d",S+i,T+i);
36 }
37 int ford(int s,int t)
38 {
39 int i,j;
40
41 for(i=1;i<=N;++i)
42 {
43 dis[i]=INF;
44 pre[i]=i;
45 }
46 dis[s]=0;
47 do{
48 flag=false;
49 for(i=1;i<=N;++i)
50 if(dis[i]<INF)
51 for(j=1;j<=N;++j)
52 if(dis[j]>dis[i]+cost[i][j])
53 {
54 dis[j]=dis[i]+cost[i][j];
55 pre[j]=i;
56 flag=true;
57 }
58 }while(flag);
59 return dis[t];
60 }
61 void dfs(int s,int t)
62 {
63 if(s==t) return;
64 dfs(s,pre[t]);
65 printf("%d->",pre[t]);
66 }
67 void solve()
68 {
69 int i;
70
71 for(i=1;i<=M;++i)
72 {
73 printf("%d\n",ford(S[i],T[i]));
74 dfs(S[i],T[i]);
75 printf("%d\n",T[i]);
76 }
77 }
78 int main()
79 {
80 freopen("zui.in","r",stdin);
81 freopen("zui.out","w",stdout);
82
83 init();
84 solve();
85 return 0;
86 }
posted on 2010-08-01 15:44
xfstart07 阅读(237)
评论(0) 编辑 收藏 引用 所属分类:
算法学习 、
图论