在加權(quán)圖中，我們經(jīng)常需要找出兩個(gè)指定點(diǎn)之間的最短路，這類問題有如下兩種形式：
1、單個(gè)點(diǎn)到圖中各個(gè)點(diǎn)的距離
2、圖中任意兩個(gè)點(diǎn)之間的距離
一、 單個(gè)點(diǎn)到圖中各個(gè)點(diǎn)的距離
這類題目主要有兩個(gè)算法：Bellman-Ford算法，時(shí)間復(fù)雜性為O(n3)，關(guān)于其算法的描述及其優(yōu)化：
Dijkstra算法，時(shí)間復(fù)雜性為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中其它各個(gè)點(diǎn)的距離最短證明：令k表示6行迭代的次數(shù)(1) 當(dāng)k=0時(shí)，即初始化后，L[u]為0，S為{u}，顯然滿足如下兩個(gè)條件：
- 對(duì)于在S中的任意頂點(diǎn)v都有L[v]為u到v的最短路的長度
- 對(duì)于不再S中的任意點(diǎn)v都有L[v]為u只經(jīng)過S中的點(diǎn)到v的最短路的長度
(2) 假設(shè)k-1次迭代后，滿足上述條件，對(duì)于第k次迭代時(shí)，選取vk作為加入S點(diǎn)。 假設(shè)L[vk]不是從u到vk的最短路的長度，由于vk不在k-1次迭代后的S中，則根據(jù)上述條件2可知在u到vk的最短路P：u=v1,v2,…,vk，中必存在一個(gè)經(jīng)過一個(gè)不在S中的點(diǎn)vi(不為vk)，使得v1,…,vi-1在S中，則L[vi]為u到vi的最短路得長度，則有L[vi]<u到vk的最短路的長度<L[vk]，這與算法第7行中vk的選取條件矛盾。證畢。
二、 圖中任意兩個(gè)點(diǎn)之間的距離
這類問題有個(gè)十分直觀的方法，就是對(duì)每個(gè)點(diǎn)運(yùn)行Dijkstra算法，時(shí)間復(fù)雜性為O(n3)，而且也是一個(gè)性能較好的方法。下面是一個(gè)著名的算法—Floyd-Warshall算法，時(shí)間復(fù)雜性也是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])
這個(gè)算法其實(shí)是一個(gè)動(dòng)態(tài)規(guī)劃的形式，令d[i, j, k]表示vi與vj經(jīng)過前k個(gè)點(diǎn)的最短距離，則可得遞歸式：
d[i, j, 0] = w[i, j] 當(dāng)vi與vj相鄰
d[i, j, 0] = ∞ 當(dāng)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 閱讀(525)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
圖論