python實(shí)現(xiàn)Dijkstra靜態(tài)尋路算法
算法介紹
迪科斯徹算法使用了廣度優(yōu)先搜索解決賦權(quán)有向圖或者無(wú)向圖的單源最短路徑問(wèn)題,算法最終得到一個(gè)最短路徑樹(shù)。該算法常用于路由算法或者作為其他圖算法的一個(gè)子模塊。
當(dāng)然目前也有人將它用來(lái)處理物流方面,以獲取代價(jià)最小的運(yùn)送方案。
算法思路
Dijkstra算法采用的是一種貪心的策略。
1.首先,聲明一個(gè)數(shù)組dis來(lái)保存源點(diǎn)到各個(gè)頂點(diǎn)的最短距離和一個(gè)保存已經(jīng)找到了最短路徑的頂點(diǎn)的集合T。
2.其次,原點(diǎn) s 的路徑權(quán)重被賦為 0 (dis[s] = 0)。若對(duì)于頂點(diǎn) s 存在能直接到達(dá)的邊(s,m),則把dis[m]設(shè)為w(s, m),同時(shí)把所有其他(s不能直接到達(dá)的)頂點(diǎn)的路徑長(zhǎng)度設(shè)為無(wú)窮大。初始時(shí),集合T只有頂點(diǎn)s。
3.從dis數(shù)組選擇最小值,則該值就是源點(diǎn)s到該值對(duì)應(yīng)的頂點(diǎn)的最短路徑,并且把該點(diǎn)加入到T中,此時(shí)完成一個(gè)頂點(diǎn)。
4.再次,看看新加入的頂點(diǎn)是否可以到達(dá)其他頂點(diǎn)并且看看通過(guò)該頂點(diǎn)到達(dá)其他點(diǎn)的路徑長(zhǎng)度是否比源點(diǎn)直接到達(dá)短,如果是,那么就替換這些頂點(diǎn)在dis中的值。
5.最后,從dis中找出最小值,重復(fù)上述動(dòng)作,直到T中包含了圖的所有頂點(diǎn)(可以到達(dá)的)。
算法圖形演示
現(xiàn)在有圖如下:
每個(gè)線的權(quán)重以及標(biāo)識(shí)如圖所示。
第一步:
建立dis數(shù)組和T數(shù)組。
首先從起點(diǎn)A 開(kāi)始,將A可以直接到達(dá)的頂點(diǎn)的權(quán)重記錄在dis數(shù)組中,無(wú)法直達(dá)的記錄無(wú)窮大(當(dāng)前使用FFFF表示無(wú)窮大)。
將當(dāng)前選擇的頂點(diǎn)加入數(shù)組T:
第二步:
從dis數(shù)組中選擇一個(gè)不在T數(shù)組中的頂點(diǎn)的最小權(quán)重值的頂點(diǎn),當(dāng)前選擇為B頂點(diǎn),并將B可以直接到達(dá)的頂點(diǎn)的相關(guān)權(quán)重和當(dāng)前dis中的權(quán)重值比較,如果當(dāng)前dis權(quán)重值大,則替換:
將B加入數(shù)組T:
第三步:
依次選擇頂點(diǎn)C:
將C加入數(shù)組T:
第四步:
依次選擇頂點(diǎn)D:
將D加入數(shù)組T:
第五步:
依次選擇頂點(diǎn)E:
將E加入數(shù)組T:
第六步:
依次選擇頂點(diǎn)F:
將F加入數(shù)組T:
因?yàn)樗械捻旤c(diǎn)都已經(jīng)在T數(shù)組中了,算法結(jié)束。
這樣就求得了從A點(diǎn)到各個(gè)頂點(diǎn)的最優(yōu)解。
可以看到A頂點(diǎn)無(wú)法直達(dá)F頂點(diǎn)。
代碼表示:
(代碼中使用999代表FFF)
#encoding:utf-8 import copy """ 圖的表示方式 鄰接矩陣 999代表無(wú)限遠(yuǎn) """ tuG=[[0, 10, 20, 999, 999, 999], [999, 0, 999, 20, 70, 999], [999, 999, 0, 50, 30, 999], [999, 999, 999, 0, 999, 999], [999, 999, 999, 10, 0, 999], [999, 999, 999, 20, 20, 0]]; tuX = 6; # 設(shè)置原點(diǎn)到其他定點(diǎn)的各個(gè)距離 dis = copy.deepcopy(tuG[0]); def Dijkstra(G,v0): """ 使用 Dijkstra 算法計(jì)算指定點(diǎn) v0 到圖 G 中任意點(diǎn)的最短路徑的距離 INF 為設(shè)定的無(wú)限遠(yuǎn)距離值 """ t = []; minv = v0; while len(t) <= tuX: t.append(minv); #以當(dāng)前點(diǎn)的中心向外擴(kuò)散 for w in range(0, tuX): if dis[minv] + G[minv][w] < dis[w]: dis[w] = dis[minv] + G[minv][w] tmp = 1000; for i in range(0, tuX): tmpFlag = False; for j in range(0, len(t)): if i == t[j]: tmpFlag = True; break; if tmpFlag == True: continue; if tmp > dis[i]: tmp = dis[i]; minv = i; if __name__ == '__main__': Dijkstra(tuG,0); print dis;
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
- Python數(shù)據(jù)結(jié)構(gòu)與算法之圖的最短路徑(Dijkstra算法)完整實(shí)例
- Python使用Dijkstra算法實(shí)現(xiàn)求解圖中最短路徑距離問(wèn)題詳解
- Python實(shí)現(xiàn)Dijkstra算法
- python實(shí)現(xiàn)dijkstra最短路由算法
- python實(shí)現(xiàn)Dijkstra算法的最短路徑問(wèn)題
- python Dijkstra算法實(shí)現(xiàn)最短路徑問(wèn)題的方法
- python3實(shí)現(xiàn)Dijkstra算法最短路徑的實(shí)現(xiàn)
- 一文教你用python編寫Dijkstra算法進(jìn)行機(jī)器人路徑規(guī)劃
- python最短路徑的求解Dijkstra算法示例代碼
相關(guān)文章
python3中的函數(shù)與參數(shù)及空值問(wèn)題
這篇文章主要介紹了python3-函數(shù)與參數(shù)以及空值,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-11-11Python標(biāo)準(zhǔn)庫(kù)之zipfile和tarfile模塊的使用
zipfile和tarfile是Python中常用的壓縮包模塊,本文將通過(guò)示例詳細(xì)講解一下這兩個(gè)模塊的使用方法,快跟隨小編一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06使用python opencv對(duì)畸變圖像進(jìn)行矯正的實(shí)現(xiàn)
本文主要介紹了使用python opencv對(duì)畸變圖像進(jìn)行矯正的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-05-05Python操作Redis數(shù)據(jù)庫(kù)的超詳細(xì)教程
大家應(yīng)該都知道redis是一個(gè)基于內(nèi)存的高效的鍵值型非關(guān)系數(shù)據(jù)庫(kù),下面這篇文章主要給大家介紹了關(guān)于Python操作Redis的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06python通過(guò)偽裝頭部數(shù)據(jù)抵抗反爬蟲(chóng)的實(shí)例
下面小編就為大家分享一篇python通過(guò)偽裝頭部數(shù)據(jù)抵抗反爬蟲(chóng)的實(shí)例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-05-05Python中優(yōu)雅使用assert斷言的方法實(shí)例
我們?cè)陂_(kāi)發(fā)一個(gè)程序時(shí)候,與其讓它運(yùn)行時(shí)崩潰,不如在它出現(xiàn)錯(cuò)誤條件時(shí)就崩潰(返回錯(cuò)誤),這時(shí)候斷言assert就顯得非常有用,這篇文章主要給大家介紹了關(guān)于Python中優(yōu)雅使用assert斷言的相關(guān)資料,需要的朋友可以參考下2021-09-09python將字符串轉(zhuǎn)變成dict格式的實(shí)現(xiàn)
這篇文章主要介紹了python將字符串轉(zhuǎn)變成dict格式的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-11-11Python計(jì)算不規(guī)則圖形面積算法實(shí)現(xiàn)解析
這篇文章主要介紹了Python計(jì)算不規(guī)則圖形面積算法實(shí)現(xiàn)解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11