本文實例講述了Python數據結構與算法之圖的最短路徑(Dijkstra算法)。分享給大家供大家參考，具體如下：

# coding:utf-8

# Dijkstra算法——通過邊實現松弛

# 指定一個點到其他各頂點的路徑——單源最短路徑

# 初始化圖參數

G = {1:{1:0, 2:1, 3:12},

2:{2:0, 3:9, 4:3},

3:{3:0, 5:5},

4:{3:4, 4:0, 5:13, 6:15},

5:{5:0, 6:4},

6:{6:0}}

# 每次找到離源點最近的一個頂點，然后以該頂點為重心進行擴展

# 最終的到源點到其余所有點的最短路徑

# 一種貪婪算法

def Dijkstra(G,v0,INF=999):

""" 使用 Dijkstra 算法計算指定點 v0 到圖 G 中任意點的最短路徑的距離

INF 為設定的無限遠距離值

此方法不能解決負權值邊的圖

"""

book = set()

minv = v0

# 源頂點到其余各頂點的初始路程

dis = dict((k,INF) for k in G.keys())

dis[v0] = 0

while len(book)

book.add(minv) # 確定當期頂點的距離

for w in G[minv]: # 以當前點的中心向外擴散

if dis[minv] + G[minv][w] < dis[w]: # 如果從當前點擴展到某一點的距離小與已知最短距離

dis[w] = dis[minv] + G[minv][w] # 對已知距離進行更新

new = INF # 從剩下的未確定點中選擇最小距離點作為新的擴散點

for v in dis.keys():

if v in book: continue

if dis[v] < new:

new = dis[v]

minv = v

return dis

dis = Dijkstra(G,v0=1)

print("腳本之家測試結果：")

print dis.values()

運行結果：

希望本文所述對大家Python程序設計有所幫助。

總結

以上是生活随笔為你收集整理的python棋盘最短路径_Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例...的全部內容，希望文章能夠幫你解決所遇到的問題。

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