python Dijkstra算法實(shí)現(xiàn)最短路徑問(wèn)題的方法
本文借鑒于張廣河教授主編的《數(shù)據(jù)結(jié)構(gòu)》,對(duì)其中的代碼進(jìn)行了完善。
從某源點(diǎn)到其余各頂點(diǎn)的最短路徑
Dijkstra算法可用于求解圖中某源點(diǎn)到其余各頂點(diǎn)的最短路徑。假設(shè)G={V,{E}}是含有n個(gè)頂點(diǎn)的有向圖,以該圖中頂點(diǎn)v為源點(diǎn),使用Dijkstra算法求頂點(diǎn)v到圖中其余各頂點(diǎn)的最短路徑的基本思想如下:
- 使用集合S記錄已求得最短路徑的終點(diǎn),初始時(shí)S={v}。
- 選擇一條長(zhǎng)度最小的最短路徑,該路徑的終點(diǎn)w屬于V-S,將w并入S,并將該最短路徑的長(zhǎng)度記為Dw。
- 對(duì)于V-S中任一頂點(diǎn)是s,將源點(diǎn)到頂點(diǎn)s的最短路徑長(zhǎng)度記為Ds,并將頂點(diǎn)w到頂點(diǎn)s的弧的權(quán)值記為Dws,若Dw+Dws<Ds,
- 則將源點(diǎn)到頂點(diǎn)s的最短路徑長(zhǎng)度修改為Dw+Ds=ws。
- 重復(fù)執(zhí)行2和3,知道S=V。
- 為了實(shí)現(xiàn)算法,
- 使用鄰接矩陣Arcs存儲(chǔ)有向網(wǎng),當(dāng)i=j時(shí),Arcs[i][j]=0;當(dāng)i!=j時(shí),若下標(biāo)為i的頂點(diǎn)到下標(biāo)為j的頂點(diǎn)有弧且弧的權(quán)值為w,則Arcs[i][j]=w,否則Arcs[i][j]=float(‘inf')即無(wú)窮大。
- 使用Dist存儲(chǔ)源點(diǎn)到每一個(gè)終點(diǎn)的最短路徑長(zhǎng)度。
- 使用列表Path存儲(chǔ)每一條最短路徑中倒數(shù)第二個(gè)頂點(diǎn)的下標(biāo)。
- 使用flag記錄每一個(gè)頂點(diǎn)是否已經(jīng)求得最短路徑,在思想中即是判斷頂點(diǎn)是屬于V集合,還是屬于V-S集合。
代碼實(shí)現(xiàn)
#構(gòu)造有向圖Graph class Graph: def __init__(self,graph,labels): #labels為標(biāo)點(diǎn)名稱 self.Arcs=graph self.VertexNum=graph.shape[0] self.labels=labels def Dijkstra(self,Vertex,EndNode): #Vertex為源點(diǎn),EndNode為終點(diǎn) Dist=[[] for i in range(self.VertexNum)] #存儲(chǔ)源點(diǎn)到每一個(gè)終點(diǎn)的最短路徑的長(zhǎng)度 Path=[[] for i in range(self.VertexNum)] #存儲(chǔ)每一條最短路徑中倒數(shù)第二個(gè)頂點(diǎn)的下標(biāo) flag=[[] for i in range(self.VertexNum)] #記錄每一個(gè)頂點(diǎn)是否求得最短路徑 index=0 #初始化 while index<self.VertexNum: Dist[index]=self.Arcs[Vertex][index] flag[index]=0 if self.Arcs[Vertex][index]<float('inf'): #正無(wú)窮 Path[index]=Vertex else: Path[index]=-1 #表示從頂點(diǎn)Vertex到index無(wú)路徑 index+=1 flag[Vertex]=1 Path[Vertex]=0 Dist[Vertex]=0 index=1 while index<self.VertexNum: MinDist=float('inf') j=0 while j<self.VertexNum: if flag[j]==0 and Dist[j]<MinDist: tVertex=j #tVertex為目前從V-S集合中找出的距離源點(diǎn)Vertex最斷路徑的頂點(diǎn) MinDist=Dist[j] j+=1 flag[tVertex]=1 EndVertex=0 MinDist=float('inf') #表示無(wú)窮大,若兩點(diǎn)間的距離小于MinDist說(shuō)明兩點(diǎn)間有路徑 #更新Dist列表,符合思想中第三條 while EndVertex<self.VertexNum: if flag[EndVertex]==0: if self.Arcs[tVertex][EndVertex]<MinDist and Dist[ tVertex]+self.Arcs[tVertex][EndVertex]<Dist[EndVertex]: Dist[EndVertex]=Dist[tVertex]+self.Arcs[tVertex][EndVertex] Path[EndVertex]=tVertex EndVertex+=1 index+=1 vertex_endnode_path=[] #存儲(chǔ)從源點(diǎn)到終點(diǎn)的最短路徑 return Dist[EndNode],start_end_Path(Path,Vertex,EndNode,vertex_endnode_path) #根據(jù)本文上述定義的Path遞歸求路徑 def start_end_Path(Path,start,endnode,path): if start==endnode: path.append(start) else: path.append(endnode) start_end_Path(Path,start,Path[endnode],path) return path if __name__=='__main__': #float('inf')表示無(wú)窮 graph=np.array([[0,6,5,float('inf'),float('inf'),float('inf')], [float('inf'),0,2,8,float('inf'),float('inf')], [float('inf'),float('inf'),0,float('inf'),3,float('inf')], [float('inf'),float('inf'),7,0,float('inf'),9], [float('inf'),float('inf'),float('inf'),float('inf'),0,9], [float('inf'),float('inf'),float('inf'),float('inf'),0]]) G=Graph(graph,labels=['a','b','c','d','e','f']) start=input('請(qǐng)輸入源點(diǎn)') endnode=input('請(qǐng)輸入終點(diǎn)') dist,path=Dijkstra(G,G.labels.index(start),G.labels.index(endnode)) Path=[] for i in range(len(path)): Path.append(G.labels[path[len(path)-1-i]]) print('從頂點(diǎn){}到頂點(diǎn){}的最短路徑為:\n{}\n最短路徑長(zhǎng)度為:{}'.format(start,endnode,Path,dist))
輸出結(jié)果如下:
請(qǐng)輸入源點(diǎn)
a
請(qǐng)輸入終點(diǎn)
f
從頂點(diǎn)a到頂點(diǎn)f的最短路徑為:
['a', 'c', 'e', 'f']
最短路徑長(zhǎng)度為:17
以上就是本文的全部?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靜態(tài)尋路算法
- python實(shí)現(xiàn)Dijkstra算法的最短路徑問(wèn)題
- python3實(shí)現(xiàn)Dijkstra算法最短路徑的實(shí)現(xiàn)
- 一文教你用python編寫Dijkstra算法進(jìn)行機(jī)器人路徑規(guī)劃
- python最短路徑的求解Dijkstra算法示例代碼
相關(guān)文章
Python中的random函數(shù)實(shí)例詳解
random模塊提供生成偽隨機(jī)數(shù)的函數(shù),在使用時(shí)需要導(dǎo)入random模塊,這篇文章主要介紹了Python中的random函數(shù),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-02-02淺談Python2之漢字編碼為unicode的問(wèn)題(即類似\xc3\xa4)
今天小編就為大家分享一篇淺談Python2之漢字編碼為unicode的問(wèn)題(即類似\xc3\xa4),具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-08-08python中列表推導(dǎo)式與生成器表達(dá)式對(duì)比詳解
python當(dāng)然不是一門編譯型語(yǔ)言,但是它還是要被解析成二進(jìn)制的字節(jié)碼才能被執(zhí)行,執(zhí)行它的正是python解釋器,下面這篇文章主要給大家介紹了關(guān)于python中列表推導(dǎo)式與生成器表達(dá)式對(duì)比的相關(guān)資料,需要的朋友可以參考下2023-01-01python+django+rest框架配置創(chuàng)建方法
今天小編就為大家分享一篇python+django+rest框架配置創(chuàng)建方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-08-08BeautifulSoup獲取指定class樣式的div的實(shí)現(xiàn)
這篇文章主要介紹了BeautifulSoup獲取指定class樣式的div的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12python利用xpath爬取網(wǎng)上數(shù)據(jù)并存儲(chǔ)到django模型中
這篇文章主要介紹了python利用xpath爬取網(wǎng)上數(shù)據(jù)并存儲(chǔ)到django模型中,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-02-02Python+PyQt5實(shí)現(xiàn)開(kāi)發(fā)Memcached客戶端
這篇文章主要介紹了如何使用Python和PyQt5來(lái)制作一個(gè)Memcached客戶端,以便我們可以輕松地與Memcached服務(wù)器進(jìn)行交互,感興趣的小伙伴可以了解一下2023-06-06