在加权图中，我们经常需要找出两个指定点之间的最短路，这类问题有如下两种形式：
1、单个点到图中各个点的距离
2、图中任意两个点之间的距离
一、 单个点到图中各个点的距离
这类题目主要有两个算法：Bellman-Ford算法，时间复杂性为O(n3)，关于其算法的描述及其优化：
Dijkstra算法，时间复杂性为O(n2)，描述如下：
1 Dijkstra(G, u)
2 for each vertex v in V(G)
3 L[v] = ∞
4 L[u] = 0
5 S = {u}
6 while S != V(G)
7 v = vertex in V(G)-S with the minimum L-value
8 S = S + {v}
9 for each vertex a in V(G)-S
10 if L[v] + w[v, a] < L[v]
11 L[v] = L[v] + w[v, a]
定理：Dijkstra算法能求出u到G中其它各个点的距离最短证明：令k表示6行迭代的次数(1) 当k=0时，即初始化后，L[u]为0，S为{u}，显然满足如下两个条件：
- 对于在S中的任意顶点v都有L[v]为u到v的最短路的长度
- 对于不再S中的任意点v都有L[v]为u只经过S中的点到v的最短路的长度
(2) 假设k-1次迭代后，满足上述条件，对于第k次迭代时，选取vk作为加入S点。 假设L[vk]不是从u到vk的最短路的长度，由于vk不在k-1次迭代后的S中，则根据上述条件2可知在u到vk的最短路P：u=v1,v2,…,vk，中必存在一个经过一个不在S中的点vi(不为vk)，使得v1,…,vi-1在S中，则L[vi]为u到vi的最短路得长度，则有L[vi]<u到vk的最短路的长度<L[vk]，这与算法第7行中vk的选取条件矛盾。证毕。
二、 图中任意两个点之间的距离
这类问题有个十分直观的方法，就是对每个点运行Dijkstra算法，时间复杂性为O(n3)，而且也是一个性能较好的方法。下面是一个著名的算法—Floyd-Warshall算法，时间复杂性也是O(n3)：
1 Warshall(G)
2 for i 1 to n
3 for j 1 to n
4 if vi in adj[vj]
5 d[i, j] = w[i, j]
6 else
7 d[i, j] = ∞
8 for k 1 to n
9 for i 1 to n
10 for j 1 to n
11 d[i, j] = min(d[i, j], d[i, k]+d[k, j])
这个算法其实是一个动态规划的形式，令d[i, j, k]表示vi与vj经过前k个点的最短距离，则可得递归式：
d[i, j, 0] = w[i, j] 当vi与vj相邻
d[i, j, 0] = ∞ 当vi与vj不相邻
d[i, j, k+1] = min(d[i, j, k], d[i, k, k]+ d[k, j, k])
posted on 2009-05-22 22:49
Icyflame 阅读(478)
评论(0) 编辑 收藏 引用 所属分类:
图论