您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)怎么在python中使用Dijkstra算法計(jì)算最短路徑,文章內(nèi)容質(zhì)量較高,因此小編分享給大家做個(gè)參考,希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。
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
關(guān)于怎么在python中使用Dijkstra算法計(jì)算最短路徑就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò),可以把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。