迪杰斯特拉（Dijkstra）算法主要是針對沒有負值的有向圖，求解其中的單一起點到其他頂點的最短路徑算法。

1 算法原理

　　迪杰斯特拉（Dijkstra）算法是一個按照路徑長度遞增的次序產生的最短路徑算法。下圖為帶權值的有向圖，作為程序中的實驗數據。

　　

　　其中，帶權值的有向圖采用鄰接矩陣graph來進行存儲，在計算中就是采用n*n的二維數組來進行存儲，v0-v5表示數組的索引編號0-5，二維數組的值表示節點之間的權值，若兩個節點不能通行，比如，v0->v1不能通行，那么graph[0,1]=+∞ （采用計算機中最大正整數來進行表示）。那如何求解從v0每個v節點的最短路徑長度呢?

　　

　　首先，引進一個輔助數組cost，它的每個值cost[i]表示當前所找到的從起始點v0到終點vi的最短路徑的權值（長度花費），該數組的初態為：若從v0到vi有弧，則cost[i]為弧上的權值，否則置cost[i]為+∞?。

　　顯然，長度為：cost[j]=Min_i(graph[0,i] | v_i in V)?的路徑就是從v0出發的長度最短的一條最短路徑。此路徑為(v_0,v_j) ，那么下次長度次短的路徑必定是弧(v_0,v_i)上的權值cost[i](v_i in V)，或者是cost[k](v_k in S)和弧(v_k,v_i)的權值之和。其中V：待求解最短路徑的節點j集合；S：已求解最短路徑的節點集合。

?

2 算法流程

　　根據上面的算法原理分析，下面描述算法的實現流程。

初始化：初始化輔助數組cost，從v0出發到圖上其余節點v的初始權值為：cost[i]=graph[0,i] ?|? v_i in V ；初始化待求節點S集合，它的初始狀態為始點，V集合，全部節點-始節點。

選擇節點v_j ，使得cost[j]=Min ( cost[i] | v_i in V -S ) ，v_j? 就是當前求的一條從v0出發的最短路徑的終點，修改S集合，使得 S=S + V_j ，修改集合V = V - V_j。

修改從v0出發到節點V-S上任一頂點 v_k 可達的最短路徑，若cost[j]+graph[j,k]<cost[k] ，則修改cost[k]為：cost[k]=cost[j]+graph[j,k] 。

重復操作2，3步驟，直到求解集合V中的所有節點為止。

　　其中最短路徑的存儲采用一個path整數數組，path[i]的值記錄vi的前一個節點的索引，通過path一直追溯到起點，就可以找到從vi到起始節點的最短路徑。比如起始節點索引為0，若path[3]=4, path[4]=0；那么節點v2的最短路徑為，v0->v4->v3。

3 算法實現

　　采用python語言對第2節中的算法流程進行實現，關鍵代碼如下。

3.1 最短路徑代碼

1 #!/bin/python 2 # -*- coding:utf-8 -*- 3 4 def dijkstra(graph, startIndex, path, cost, max): 5 """ 6 求解各節點最短路徑，獲取path，和cost數組， 7 path[i] 表示vi節點的前繼節點索引，一直追溯到起點。 8 cost[i] 表示vi節點的花費 9 """ 10 lenth = len(graph) 11 v = [0] * lenth 12 # 初始化 path，cost，V 13 for i in range(lenth): 14 if i == startIndex: 15 v[startIndex] = 1 16 else: 17 cost[i] = graph[startIndex][i] 18 path[i] = (startIndex if (cost[i] < max) else -1) 19 # print v, cost, path 20 for i in range(1, lenth): 21 minCost = max 22 curNode = -1 23 for w in range(lenth): 24 if v[w] == 0 and cost[w] < minCost: 25 minCost = cost[w] 26 curNode = w 27 # for 獲取最小權值的節點 28 if curNode == -1: break 29 # 剩下都是不可通行的節點，跳出循環 30 v[curNode] = 1 31 for w in range(lenth): 32 if v[w] == 0 and (graph[curNode][w] + cost[curNode] < cost[w]): 33 cost[w] = graph[curNode][w] + cost[curNode] # 更新權值 34 path[w] = curNode # 更新路徑 35 # for 更新其他節點的權值（距離）和路徑 36 return path 37 38 if __name__ == '__main__': 39 max = 2147483647 40 graph = [ 41 [max, max, 10, max, 30, 100], 42 [max, max, 5, max, max, max], 43 [max, max, max, 50, max, max], 44 [max, max, max, max, max, 10], 45 [max, max, max, 20, max, 60], 46 [max, max, max, max, max, max], 47 ] 48 path = [0] * 6 49 cost = [0] * 6 50 print dijkstra(graph, 0, path, cost, max)

4 運行結果

1 [0, -1, 0, 4, 0, 3]

?

轉載于:https://www.cnblogs.com/mayunting/p/10426705.html

總結

以上是生活随笔為你收集整理的最短路径问题-Dijkstra算法的python实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。