怎么使用Dijkstra算法

怎么使用Dijkstra算法，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

最短路問題

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

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

Dijkstra算法

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

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

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

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

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

我們還是以上面的圖為例

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

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

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

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

n = 4 #4個點 # 初始化 visited  visitd = [0] * (n) #記錄該點是否為訪問過 # 第一個點已經訪問了 visitd[0] = 1 #初始化源點到各個點的距離 node 集合 d = g[0]  for i in range(2, n):     # 遍歷d 取出權重最小節點的位置     minWeigth = MAX     for j in range(2, n):         if d[j] < minWeigth and visitd[j] == 0:             minWeigth = d[j]             k = j             # 表示k是當前距1最短的點，同時標記k已經被找過     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

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

「把Dijkstra 算法應用于無權圖，或者所有邊的權都相等的圖，Dijkstra 算法等同于BFS搜索。」

多點求解

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

import math # 假設圖中的頂點數 V = 6 # 標記數組：used[v]值為False說明改頂點還沒有訪問過，在S中，否則在U中！ used = [False for _ in range(V)] # 距離數組：distance[i]表示從源點s到ｉ的最短距離，distance[s]=0 distance = [float('inf') for _ in range(V)] # cost[u][v]表示邊e=(u,v)的權值，不存在時設為INF # cost領接表 cost = [[float('inf') for _ in range(V)] for _ in range(V)]  def dijkstra(s):     distance[s] = 0     while True:         # v在這里相當于是一個哨兵，對包含起點s做統一處理！         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算法使用鄰接表的時間復雜度是。因此，很多使用堆進行優化或者使用散列表對多余的空間進行優化。

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。