[圖]最短路徑-Dijkstra演算法
- 2020 年 3 月 13 日
- 筆記
迪傑斯特拉演算法(Dijkstra)是由荷蘭電腦科學家狄克斯特拉於1959 年提出的，因此又叫狄克斯特拉演算法。是從一個頂點到其餘各頂點的最短路徑演算法，解決的是有權圖中最短路徑問題。迪傑斯特拉演算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。 -來自百度百科
一.最短路徑問題的求解
1、單源最短路徑用Dijkstra演算法；
2、所有頂點間的最短路徑用Floyd演算法。
二.Dijkstra演算法
開始之前我們需要知道的一些知識點：
1.Dijkstra演算法只能用於邊權為正的圖中，時間複雜度為O(n^2)；
2.BFS可能會是Dijkstra演算法的實質，BFS使用的是隊列進行操作，而Dijkstra採用的是優先隊列。
Dijikstra演算法所求解的問題是：大概有這樣一個有權圖，Dijkstra演算法可以計算任意節點到其他節點的最短路徑。
案例圖
1.演算法思路
1.指定一個節點，例如我們要計算 'A' 到其他節點的最短路徑；
2.引入兩個集合（S、U），S集合包含已求出的最短路徑的點（以及相應的最短長度），U集合包含未求出最短路徑的點（以及A到該點的路徑，注意 如上圖所示，A->C由於沒有直接相連 初始時為∞）；
3.初始化兩個集合，S集合初始時 只有當前要計算的節點，A->A = 0；
4.U集合初始時為 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞；
5.從U集合中找出路徑最短的點，加入S集合，例如 A->D = 2；
6.更新U集合路徑，if ( 'D 到 B,C,E 的距離' + 'AD 距離' < 'A 到 B,C,E 的距離' ) 則更新U；
7.循環執行 4、5 兩步驟，直至遍歷結束，得到A 到其他節點的最短路徑。
2.演算法圖解
1.選定A節點並初始化，如上述步驟3所示；
圖解1
2.執行上述 4、5兩步驟，找出U集合中路徑最短的節點D 加入S集合，並根據條件 if ( 'D 到 B,C,E 的距離' + 'AD 距離' < 'A 到 B,C,E 的距離' ) 來更新U集合；
圖解2
3.這時候 A->B, A->C 都為3，沒關係。其實這時候他倆都是最短距離，如果從演算法邏輯來講的話，會先取到B點。而這個時候 if 條件變成了 if ( 'B 到 C,E 的距離' + 'AB 距離' < 'A 到 C,E 的距離' ) ，如圖所示這時候A->B距離 其實為 A->D->B；
圖解3
4.思路就是這樣，往後就是大同小異了；
圖解4
5.演算法結束。
圖解5
採用表格表示為：
<a href="https://study.sqdxwz.com/usr/uploads/2019/10/3387651027.jpg" class="highslide" onclick="return hs.expand(this,{slideshowGroup:'images'})"><img src="https://study.sqdxwz.com/usr/uploads/2019/10/3387651027.jpg" height="330" width="495"></a>
3.程式碼實現（python）
# dijkstra演算法實現，有向圖和路由的源點作為函數的輸入，最短路徑最為輸出 def dijkstra(graph,src): # 判斷圖是否為空，如果為空直接退出 if graph is None: return None nodes = [i for i in range(len(graph))] # 獲取圖中所有節點 visited=[] # 表示已經路由到最短路徑的節點集合 if src in nodes: visited.append(src) nodes.remove(src) else: return None distance={src:0} # 記錄源節點到各個節點的距離 for i in nodes: distance[i]=graph[src][i] # 初始化 # print(distance) path={src:{src:[]}} # 記錄源節點到每個節點的路徑 k=pre=src while nodes: mid_distance=float('inf') for v in visited: for d in nodes: new_distance = graph[src][v]+graph[v][d] if new_distance < mid_distance: mid_distance=new_distance graph[src][d]=new_distance # 進行距離更新 k=d pre=v distance[k]=mid_distance # 最短路徑 path[src][k]=[i for i in path[src][pre]] path[src][k].append(k) # 更新兩個節點集合 visited.append(k) nodes.remove(k) print(visited,nodes) # 輸出節點的添加過程 return distance,path if __name__ == '__main__': graph_list = [ [0, 2, 1, 4, 5, 1], [1, 0, 4, 2, 3, 4], [2, 1, 0, 1, 2, 4], [3, 5, 2, 0, 3, 3], [2, 4, 3, 4, 0, 1], [3, 4, 7, 3, 1, 0]] distance,path= dijkstra(graph_list, 0) # 查找從源點0開始帶其他節點的最短路徑 print(distance,path)
