這篇文章將為大家詳細(xì)講解有關(guān)怎么在python中利用字典實(shí)現(xiàn)最短路徑算法,文章內(nèi)容質(zhì)量較高,因此小編分享給大家做個(gè)參考,希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。
“專業(yè)、務(wù)實(shí)、高效、創(chuàng)新、把客戶的事當(dāng)成自己的事”是我們每一個(gè)人一直以來(lái)堅(jiān)持追求的企業(yè)文化。 創(chuàng)新互聯(lián)公司是您可以信賴的網(wǎng)站建設(shè)服務(wù)商、專業(yè)的互聯(lián)網(wǎng)服務(wù)提供商! 專注于成都做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、軟件開發(fā)、設(shè)計(jì)服務(wù)業(yè)務(wù)。我們始終堅(jiān)持以客戶需求為導(dǎo)向,結(jié)合用戶體驗(yàn)與視覺(jué)傳達(dá),提供有針對(duì)性的項(xiàng)目解決方案,提供專業(yè)性的建議,創(chuàng)新互聯(lián)建站將不斷地超越自我,追逐市場(chǎng),引領(lǐng)市場(chǎng)!然后再貼代碼:
_=inf=999999#inf def Dijkstra_all_minpath(start,matrix): length=len(matrix)#該圖的節(jié)點(diǎn)數(shù) path_array=[] temp_array=[] path_array.extend(matrix[start])#深復(fù)制 temp_array.extend(matrix[start])#深復(fù)制 temp_array[start] = inf#臨時(shí)數(shù)組會(huì)把處理過(guò)的節(jié)點(diǎn)的值變成inf,表示不是最小權(quán)值的節(jié)點(diǎn)了 already_traversal=[start]#start已處理 path_parent=[start]*length#用于畫路徑,記錄此路徑中該節(jié)點(diǎn)的父節(jié)點(diǎn) while(len(already_traversal)<length): i= temp_array.index(min(temp_array))#找最小權(quán)值的節(jié)點(diǎn)的坐標(biāo) temp_array[i]=inf path=[]#用于畫路徑 path.append(str(i)) k=i while(path_parent[k]!=start):#找該節(jié)點(diǎn)的父節(jié)點(diǎn)添加到path,直到父節(jié)點(diǎn)是start path.append(str(path_parent[k])) k=path_parent[k] path.append(str(start)) path.reverse()#path反序產(chǎn)生路徑 print(str(i)+':','->'.join(path))#打印路徑 already_traversal.append(i)#該索引已經(jīng)處理了 for j in range(length):#這個(gè)不用多說(shuō)了吧 if j not in already_traversal: if (path_array[i]+matrix[i][j])<path_array[j]: path_array[j] = temp_array[j] =path_array[i]+matrix[i][j] path_parent[j]=i#說(shuō)明父節(jié)點(diǎn)是i return path_array #領(lǐng)接矩陣 adjacency_matrix=[[0,10,_,30,100], [10,0,50,_,_], [_,50,0,20,10], [30,_,20,0,60], [100,_,10,60,0] ] print(Dijkstra_all_minpath(4,adjacency_matrix))
然后輸出:
2: 4->2
3: 4->2->3
0: 4->2->3->0
1: 4->2->1
[60, 60, 10, 30, 0]
主要是這樣輸出的話比較好看,然后這樣算是直接算一個(gè)點(diǎn)到所有點(diǎn)的最短路徑吧。那么寫下字典實(shí)現(xiàn)吧
def Dijkstra_all_minpath_for_graph(start,graph): inf = 999999 # inf length=len(graph) path_graph={k:inf for k in graph.keys()} already_traversal=set() path_graph[start]=0 min_node=start#初始化最小權(quán)值點(diǎn) already_traversal.add(min_node)#把找到的最小節(jié)點(diǎn)添加進(jìn)去 path_parent={k:start for k in graph.keys()} while(len(already_traversal)<=length): p = min_node if p!=start: path = [] path.append(str(p)) while (path_parent[p] != start):#找該節(jié)點(diǎn)的父節(jié)點(diǎn)添加到path,直到父節(jié)點(diǎn)是start path.append(str(path_parent[p])) p=path_parent[p] path.append(str(start)) path.reverse()#反序 print(str(min_node) + ':', '->'.join(path))#打印 if(len(already_traversal)==length):break for k in path_graph.keys():#更新距離 if k not in already_traversal: if k in graph[min_node].keys() and (path_graph[min_node]+graph[min_node][k])<path_graph[k]: path_graph[k]=path_graph[min_node]+graph[min_node][k] path_parent[k]=min_node min_value=inf for k in path_graph.keys():#找最小節(jié)點(diǎn) if k not in already_traversal: if path_graph[k]<min_value: min_node=k min_value=path_graph[k] already_traversal.add(min_node)#把找到最小節(jié)點(diǎn)添加進(jìn)去 return path_graph adjacency_graph={0:{1:10,3:30,4:100}, 1:{0:10,2:50}, 2:{1:50,3:20,4:10}, 3:{0:30,2:20,4:60}, 4:{0:100,2:10,3:60}} print(Dijkstra_all_minpath_for_graph(4,adjacency_graph))
輸出:
2: 4->2
3: 4->2->3
0: 4->2->3->0
1: 4->2->1
{0: 60, 1: 60, 2: 10, 3: 30, 4: 0}
關(guān)于怎么在python中利用字典實(shí)現(xiàn)最短路徑算法就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò),可以把它分享出去讓更多的人看到。
網(wǎng)站名稱:怎么在python中利用字典實(shí)現(xiàn)最短路徑算法-創(chuàng)新互聯(lián)
本文URL:http://bm7419.com/article4/ighie.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、微信小程序、做網(wǎng)站、企業(yè)網(wǎng)站制作、網(wǎng)站改版
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容