python中怎么利用Dijkstra算法求最短路徑，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來(lái)學(xué)習(xí)下，希望你能有所收獲。

創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比儀隴網(wǎng)站開(kāi)發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式儀隴網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋儀隴地區(qū)。費(fèi)用合理售后完善，10多年實(shí)體公司更值得信賴。

從某源點(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

則將源點(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

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無(wú)路徑

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') #表示無(wú)窮大，若兩點(diǎn)間的距離小于MinDist說(shuō)明兩點(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:無(wú)錫婦科醫(yī)院哪家好 http://www.xasgfk.cn/

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

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對(duì)創(chuàng)新互聯(lián)的支持。