在加權圖中，我們經常需要找出兩個指定點之間的最短路，這類問題有如下兩種形式：
1、單個點到圖中各個點的距離
2、圖中任意兩個點之間的距離
一、 單個點到圖中各個點的距離
這類題目主要有兩個算法：Bellman-Ford算法，時間復雜性為O(n3)，關于其算法的描述及其優(yōu)化：
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行迭代的次數(shù)(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中，則根據(jù)上述條件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])
這個算法其實是一個動態(tài)規(guī)劃的形式，令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 閱讀(497)
評論(0) 編輯 收藏 引用 所屬分類:
圖論