[[386543]]

 在上次寫道關(guān)于數(shù)據(jù)結(jié)構(gòu)的圖，圖的算法的考點只有一個：最短路問題。

最短路問題

最短路問題(Shortest Path Problems)：給定一個網(wǎng)絡(luò)，網(wǎng)絡(luò)的邊上有權(quán)重，找一條從給定起點到給定終點的路徑使路徑上的邊權(quán)重總和最小。

比如上圖的：圖中點1到點4的最短路徑長度應(yīng)為3(從1到2到4)。

最短路問題常用Dijkstra算法解決

Dijkstra算法

Dijkstra算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

比如，上圖Dijkstra算法就是不斷地尋找開始節(jié)點到鄰居節(jié)點的所有的路徑，將最初的距離設(shè)置為最短距離，然后不斷的更新節(jié)鄰居節(jié)點的最短距離，直到最遠的節(jié)點的最短距離求解出來的過程。

文字描述不清楚，看下面的動圖。

將圖上的頂點分為已訪問visited和未訪問node兩個集合。

每次從visited向外拓展一個點，拓展規(guī)則是在可更新的點里是距離最小的。

我們還是以上面的圖為例

先用鄰接矩陣表示無向圖：

MAX = 9999 
 
g= [ 
    [0, 1, 4, 6], 
    [MAX, 0, MAX, 2], 
    [MAX, MAX, 0, 1], 
    [MAX, MAX, MAX, 0] 
] 

鄰接矩陣g[0][1]=1表示，第一個節(jié)點到第二個節(jié)點的距離是1。

目的是要求出開始點1到其他各個點的最小路徑距離

n = 4 #4個點 
# 初始化 visited  
visitd = [0] * (n) #記錄該點是否為訪問過 
# 第一個點已經(jīng)訪問了 
visitd[0] = 1 
#初始化源點到各個點的距離 node 集合 
d = g[0] 
 
for i in range(2, n): 
    # 遍歷d 取出權(quán)重最小節(jié)點的位置 
    minWeigth = MAX 
    for j in range(2, n): 
        if d[j] < minWeigth and visitd[j] == 0: 
            minWeigth = d[j] 
            k = j 
            # 表示k是當(dāng)前距1最短的點，同時標記k已經(jīng)被找過 
    visitd[k] = 1 
    #  用該點進行松弛(relax) 
    for j in range(2, n): 
        if d[j] > d[k] + g[k][j] and visitd[j] == 0: 
            d[j] = d[k] + g[k][j] 
 
for i in range(1,n): 
    print(d[i]) 
     
1 
4 
5 

至此，得到節(jié)點1到其余三個節(jié)點的最短距離是1、4和5。

「把Dijkstra 算法應(yīng)用于無權(quán)圖，或者所有邊的權(quán)都相等的圖，Dijkstra 算法等同于BFS搜索。」

多點求解

在很多的時候，要求輸入一組點，然后求出輸入一個起始點，得到無向圖最短路徑。

import math 
# 假設(shè)圖中的頂點數(shù) 
V = 6 
# 標記數(shù)組：used[v]值為False說明改頂點還沒有訪問過，在S中，否則在U中！ 
used = [False for _ in range(V)] 
# 距離數(shù)組：distance[i]表示從源點s到ｉ的最短距離，distance[s]=0 
distance = [float('inf') for _ in range(V)] 
# cost[u][v]表示邊e=(u,v)的權(quán)值，不存在時設(shè)為INF 
# cost領(lǐng)接表 
cost = [[float('inf') for _ in range(V)] for _ in range(V)] 
 
def dijkstra(s): 
    distance[s] = 0 
    while True: 
        # v在這里相當(dāng)于是一個哨兵，對包含起點s做統(tǒng)一處理！ 
        v = -1 
        # 從未使用過的頂點中選擇一個距離最小的頂點 
        for u in range(V): 
            if not used[u] and (v == -1 or distance[u] < distance[v]): 
                v = u 
        if v == -1: 
            # 說明所有頂點都維護到S中了！ 
            break 
        # 將選定的頂點加入到S中, 同時進行距離更新 
        used[v] = True 
        # 更新U中各個頂點到起點s的距離。之所以更新U中頂點的距離，是由于上一步中確定了k是求出最短路徑的頂點，從而可以利用k來更新其它頂點的距離；例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。 
        for u in range(V): 
            distance[u] = min(distance[u], distance[v] + cost[v][u]) 
 
 
for _ in range(9): 
    v, u, w = list(map(int, input().split())) 
    cost[v][u] = w 
    cost[u][v] = w 
s = int(input('請輸入一個起始點：')) 
dijkstra(s) 
print(distance) 

測試用例

0 1 1 
0 2 2 
0 3 3 
1 4 7 
1 5 9 
2 4 4 
3 4 5 
3 5 6 
4 5 8 
請輸入一個起始點：0 
[0, 1, 2, 3, 6, 9] 

在測試用例中的0 1 1表示第一個頂點到第二個頂點的距離是1。

Dijkstra算法使用鄰接表的時間復(fù)雜度是。因此，很多使用堆進行優(yōu)化或者使用散列表對多余的空間進行優(yōu)化。