快捷導(dǎo)航

Python數(shù)據(jù)結(jié)構(gòu)與算法之圖的最短路徑(Dijkstra算法)完整實(shí)例

更新時(shí)間：2017年12月12日 11:30:36 作者：hanahimi

這篇文章主要介紹了Python數(shù)據(jù)結(jié)構(gòu)與算法之圖的最短路徑(Dijkstra算法),結(jié)合完整實(shí)例形式分析了Python圖的最短路徑算法相關(guān)原理與實(shí)現(xiàn)技巧,需要的朋友可以參考下

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

# coding:utf-8
# Dijkstra算法——通過(guò)邊實(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è)定的無(wú)限遠(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 dis
dis = Dijkstra(G,v0=1)
print("腳本之家測(cè)試結(jié)果：")
print dis.values()

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

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

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

您可能感興趣的文章:

相關(guān)文章

Python PEP8代碼規(guī)范常見(jiàn)問(wèn)題以及解決方案
PEP8是Python的代碼規(guī)范,本文總結(jié)了常見(jiàn)的PEP8代碼規(guī)范問(wèn)題及解決方法,幫助開(kāi)發(fā)者編寫(xiě)規(guī)范的代碼
2024-11-11
簡(jiǎn)單了解django orm中介模型
這篇文章主要介紹了簡(jiǎn)單了解django orm中介模型,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2019-07-07
python列表每個(gè)元素同增同減和列表元素去空格的實(shí)例
今天小編就為大家分享一篇python列表每個(gè)元素同增同減和列表元素去空格的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2019-07-07
使用Cython加密Python代碼防止反編譯
本文我們主要介紹如何使用 Cython 加密源代碼,雖然 Cython 的作用主要是為了提高代碼的運(yùn)行效率,但是也對(duì)源代碼有一定的加密效果,需要的朋友可以參考下
2024-05-05
python怎么調(diào)用自己的函數(shù)
在本篇文章里小編給大家分享了關(guān)于python調(diào)用自己的函數(shù)的實(shí)例方法，有興趣的朋友們可以學(xué)習(xí)參考下。
2020-07-07
安裝conda搭建python環(huán)境保姆級(jí)教程(超詳細(xì)!)
這篇文章主要給大家介紹了關(guān)于安裝conda搭建python環(huán)境保姆級(jí)教程的相關(guān)資料,conda可以理解為一個(gè)工具,也是一個(gè)可執(zhí)行命令,其核心功能是包管理和環(huán)境管理,需要的朋友可以參考下
2023-11-11
Python入門(mén)教程(七)Python數(shù)字類(lèi)型
這篇文章主要介紹了Python入門(mén)教程(七)Python數(shù)字類(lèi)型,Python是一門(mén)非常強(qiáng)大好用的語(yǔ)言,也有著易上手的特性,本文為入門(mén)教程,需要的朋友可以參考下
2023-04-04
Puppeteer使用示例詳解
這篇文章主要介紹了Puppeteer使用示例詳解，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
2019-06-06
基于PyQT實(shí)現(xiàn)區(qū)分左鍵雙擊和單擊
這篇文章主要介紹了基于PyQT實(shí)現(xiàn)區(qū)分左鍵雙擊和單擊,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2020-05-05
利用Python第三方庫(kù)實(shí)現(xiàn)預(yù)測(cè)NBA比賽結(jié)果
今天給大家?guī)?lái)的是關(guān)于Python的相關(guān)知識(shí),文章圍繞著利用Python實(shí)現(xiàn)預(yù)測(cè)NBA比賽結(jié)果展開(kāi),文中有非常詳細(xì)的介紹,需要的朋友可以參考下
2021-06-06