python如何用Dijkstra算法實(shí)現(xiàn)最短路徑？

　　這篇文章主要介紹了python Dijkstra算法實(shí)現(xiàn)最短路徑問題的方法,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

　　從某源點(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)K線圖的跳空，初始時(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

　　則將源點(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’)即無窮大。

　　使用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

　　Dist[index]=self.Arcs[Vertex][index]

　　flag[index]=0

　　if self.Arcs[Vertex][index]

　　Path[index]=Vertex

　　else:

　　Path[index]=-1 #表示從頂點(diǎn)Vertex到index無路徑

　　index+=1

　　flag[Vertex]=1

　　Path[Vertex]=0

　　Dist[Vertex]=0

　　index=1

　　while index

　　MinDist=float('inf')

　　j=0

　　while j

　　if flag[j]==0 and Dist[j]

　　tVertex=j #tVertex為目前從V-S集合中找出的距離源點(diǎn)Vertex最斷路徑的頂點(diǎn)

　　MinDist=Dist[j]

　　j+=1

　　flag[tVertex]=1

　　EndVertex=0

　　MinDist=float('inf') #表示無窮大，若兩點(diǎn)間的距離小于MinDist說明兩點(diǎn)間有路徑

　　#更新Dist列表，符合思想中第三條

　　while EndVertex

　　if flag[EndVertex]==0:

　　if self.Arcs[tVertex][EndVertex]

　　tVertex]+self.Arcs[tVertex][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')表示無窮

　　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