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

# coding:utf-8# Dijkstra算法——通過邊實(shí)現(xiàn)松弛# 指定一個(gè)點(diǎn)到其他各頂點(diǎn)的路徑——單源最短路徑# 初始化圖參數(shù)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}}# 每次找到離源點(diǎn)最近的一個(gè)頂點(diǎn)，然后以該頂點(diǎn)為重心進(jìn)行擴(kuò)展# 最終的到源點(diǎn)到其余所有點(diǎn)的最短路徑# 一種貪婪算法def Dijkstra(G,v0,INF=999): """ 使用 Dijkstra 算法計(jì)算指定點(diǎn) v0 到圖 G 中任意點(diǎn)的最短路徑的距離  INF 為設(shè)定的無限遠(yuǎn)距離值  此方法不能解決負(fù)權(quán)值邊的圖 """ book = set() minv = v0 # 源頂點(diǎn)到其余各頂點(diǎn)的初始路程 dis = dict((k,INF) for k in G.keys()) dis[v0] = 0 while len(book)<len(G):  book.add(minv)         # 確定當(dāng)期頂點(diǎn)的距離  for w in G[minv]:        # 以當(dāng)前點(diǎn)的中心向外擴(kuò)散   if dis[minv] + G[minv][w] < dis[w]:   # 如果從當(dāng)前點(diǎn)擴(kuò)展到某一點(diǎn)的距離小與已知最短距離    dis[w] = dis[minv] + G[minv][w]   # 對(duì)已知距離進(jìn)行更新  new = INF          # 從剩下的未確定點(diǎn)中選擇最小距離點(diǎn)作為新的擴(kuò)散點(diǎn)  for v in dis.keys():   if v in book: continue   if dis[v] < new:    new = dis[v]    minv = v return disdis = Dijkstra(G,v0=1)print("武林站長站測(cè)試結(jié)果：")print dis.values()

運(yùn)行結(jié)果：

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》

希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。