[[386543]]

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

最短路問(wèn)題

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

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

最短路問(wèn)題常用Dijkstra算法解決

Dijkstra算法

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

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

文字描述不清楚，看下面的動(dòng)圖。

將圖上的頂點(diǎn)分為已訪問(wèn)visited和未訪問(wèn)node兩個(gè)集合。

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

我們還是以上面的圖為例

先用鄰接矩陣表示無(wú)向圖：

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

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

目的是要求出開(kāi)始點(diǎn)1到其他各個(gè)點(diǎn)的最小路徑距離

n = 4 #4個(gè)點(diǎn) 
# 初始化 visited  
visitd = [0] * (n) #記錄該點(diǎn)是否為訪問(wèn)過(guò) 
# 第一個(gè)點(diǎn)已經(jīng)訪問(wèn)了 
visitd[0] = 1 
#初始化源點(diǎn)到各個(gè)點(diǎn)的距離 node 集合 
d = g[0] 
 
for i in range(2, n): 
    # 遍歷d 取出權(quán)重最小節(jié)點(diǎn)的位置 
    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最短的點(diǎn)，同時(shí)標(biāo)記k已經(jīng)被找過(guò) 
    visitd[k] = 1 
    #  用該點(diǎn)進(jìn)行松弛(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é)點(diǎn)1到其余三個(gè)節(jié)點(diǎn)的最短距離是1、4和5。

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

多點(diǎn)求解

在很多的時(shí)候，要求輸入一組點(diǎn)，然后求出輸入一個(gè)起始點(diǎn)，得到無(wú)向圖最短路徑。

import math 
# 假設(shè)圖中的頂點(diǎn)數(shù) 
V = 6 
# 標(biāo)記數(shù)組：used[v]值為False說(shuō)明改頂點(diǎn)還沒(méi)有訪問(wèn)過(guò)，在S中，否則在U中！ 
used = [False for _ in range(V)] 
# 距離數(shù)組：distance[i]表示從源點(diǎn)s到ｉ的最短距離，distance[s]=0 
distance = [float('inf') for _ in range(V)] 
# cost[u][v]表示邊e=(u,v)的權(quán)值，不存在時(shí)設(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)于是一個(gè)哨兵，對(duì)包含起點(diǎn)s做統(tǒng)一處理！ 
        v = -1 
        # 從未使用過(guò)的頂點(diǎn)中選擇一個(gè)距離最小的頂點(diǎn) 
        for u in range(V): 
            if not used[u] and (v == -1 or distance[u] < distance[v]): 
                v = u 
        if v == -1: 
            # 說(shuō)明所有頂點(diǎn)都維護(hù)到S中了！ 
            break 
        # 將選定的頂點(diǎn)加入到S中, 同時(shí)進(jìn)行距離更新 
        used[v] = True 
        # 更新U中各個(gè)頂點(diǎn)到起點(diǎn)s的距離。之所以更新U中頂點(diǎn)的距離，是由于上一步中確定了k是求出最短路徑的頂點(diǎn)，從而可以利用k來(lái)更新其它頂點(diǎn)的距離；例如，(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('請(qǐng)輸入一個(gè)起始點(diǎn)：')) 
dijkstra(s) 
print(distance) 

測(cè)試用例

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 
請(qǐng)輸入一個(gè)起始點(diǎn)：0 
[0, 1, 2, 3, 6, 9] 

在測(cè)試用例中的0 1 1表示第一個(gè)頂點(diǎn)到第二個(gè)頂點(diǎn)的距離是1。

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