八十七、探究最短路問題：Dijkstra算法

「@Author：Runsen」

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

最短路問題

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

比如上圖的：圖中點1到點4的最短路徑長度應為3（從1到2到4）。

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

Dijkstra算法

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

比如，上圖Dijkstra算法就是不斷地尋找開始節(jié)點到鄰居節(jié)點的所有的路徑，將最初的距離設置為最短距離，然后不斷的更新節(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是當前距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 算法應用于無權(quán)圖，或者所有邊的權(quán)都相等的圖，Dijkstra 算法等同于BFS搜索?！?/strong>

多點求解

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

import math
# 假設圖中的頂點數(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)值，不存在時設為INF
# cost領接表
cost = [[float('inf') for _ in range(V)] for _ in range(V)]

def dijkstra(s):
    distance[s] = 0
    while True:
        # v在這里相當于是一個哨兵，對包含起點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算法使用鄰接表的時間復雜度是。因此，很多使用堆進行優(yōu)化或者使用散列表對多余的空間進行優(yōu)化。