Python數(shù)據(jù)結構與算法之圖的最短路徑(Dijkstra算法)完整實例
更新時間：2017年12月12日 11:30:36 作者：hanahimi
這篇文章主要介紹了Python數(shù)據(jù)結構與算法之圖的最短路徑(Dijkstra算法),結合完整實例形式分析了Python圖的最短路徑算法相關原理與實現(xiàn)技巧,需要的朋友可以參考下
本文實例講述了Python數(shù)據(jù)結構與算法之圖的最短路徑(Dijkstra算法)。分享給大家供大家參考，具體如下：
# coding:utf-8
# Dijkstra算法——通過邊實現(xià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}}
# 每次找到離源點最近的一個頂點，然后以該頂點為重心進行擴展
# 最終的到源點到其余所有點的最短路徑
# 一種貪婪算法
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)<len(G):
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相關內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數(shù)使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》
希望本文所述對大家Python程序設計有所幫助。
您可能感興趣的文章:
相關文章
使用python編寫簡單的小程序編譯成exe跑在win10上
這篇文章主要介紹了使用python編寫簡單的小程序編譯成exe跑在win10上的相關資料,需要的朋友可以參考下2018-01-01
python報錯解決之python運行bat文件的各種問題處理
這篇文章主要介紹了python報錯解決之python運行bat文件的各種問題處理,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06
在本篇文章里小編給大家整理的是一篇關于Python中os模塊的實例用法，有興趣的朋友們可以學習下。2021-06-06
這篇文章主要介紹了Python 3 判斷2個字典相同,文中給大家提到了Python3 查找兩字典的相同點問題及解決方法，需要的朋友可以參考下2019-08-08
Python Pandas中合并數(shù)據(jù)的5個函數(shù)使用詳解
數(shù)據(jù)合并是數(shù)據(jù)處理過程中的必經(jīng)環(huán)節(jié)，pandas作為數(shù)據(jù)分析的利器，提供了五種常用的數(shù)據(jù)合并方式，讓我們看看如何使用這些方法吧！2022-05-05
Python selenium鍵盤鼠標事件實現(xiàn)過程詳解
這篇文章主要介紹了Python selenium鍵盤鼠標事件實現(xiàn)過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-07-07
Python+Pygame實現(xiàn)經(jīng)典魂斗羅游戲
《魂斗羅》（Contra）是由Konami于1987年推出的一系列卷軸射擊類單機游戲。本文將利用Python中的Pygame庫實現(xiàn)這一經(jīng)典游戲，感興趣的可以了解一下2022-05-05
selenium+Chrome滑動驗證碼破解二(某某網(wǎng)站)
這篇文章主要介紹了selenium+Chrome滑動驗證碼破解二(某某網(wǎng)站)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-12-12
這篇文章主要為大家介紹了Python采集電影評論實現(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04
這篇文章主要為大家介紹了Java開發(fā)者快速進修Python指南之簡易跳表示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12