基于Python實(shí)現(xiàn)迪杰斯特拉和弗洛伊德算法
更新時(shí)間：2020年05月27日 15:06:14 作者：BUAA-XX
這篇文章主要為大家詳細(xì)介紹了基于Python實(shí)現(xiàn)迪杰斯特拉和弗洛伊德算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
圖搜索之基于Python的迪杰斯特拉算法和弗洛伊德算法，供大家參考，具體內(nèi)容如下
Djstela算法
#encoding=UTF-8
MAX=9
'''
Created on 2016年9月28日
@author: sx
'''
b=999
G=[[0,1,5,b,b,b,b,b,b],\
[1,0,3,7,5,b,b,b,b],\
[5,3,0,b,1,7,b,b,b],\
[b,7,b,0,2,b,3,b,b],\
[b,5,1,2,0,3,6,9,b],\
[b,b,7,b,3,0,b,5,b],\
[b,b,b,3,6,b,0,2,7],\
[b,b,b,b,9,5,2,0,4],\
[b,b,b,b,b,b,7,4,0]]
P=[]
D=[]
def Djstela(G,P,D):
final=[]
for i in range(0,len(G)):
final.append(0)
D.append(G[0][i])
P.append(0)
D[0]=0
final[0]=1
k=0
for v in range(1,len(G)):
min=999
for w in range(0,len(G)):
if final[w]==0 and D[w]<min:
k=w
min=D[w]
final[k]=1
for t in range(0,len(G)):
if min+G[k][t]<D[t]:
D[t]=min+G[k][t]
P[t]=k
print("\n最短路徑\n",D,"\n","\n前一個(gè)選擇\n",P)
def search(x):
print("選擇的終點(diǎn)",x,"最短路徑",D[x])
print("鄰接矩陣\n")
for i in range(0,9):
print(G[i])
Djstela(G, P, D)
q=input("\n請(qǐng)輸入終點(diǎn)")
search(int(q))
FLOYD算法
#encoding=UTF-8
'''
Created on 2016年9月28日
@author: sx
'''
t=0
b=999
G=[[0,1,5,b,b,b,b,b,b],\
[1,0,3,7,5,b,b,b,b],\
[5,3,0,b,1,7,b,b,b],\
[b,7,b,0,2,b,3,b,b],\
[b,5,1,2,0,3,6,9,b],\
[b,b,7,b,3,0,b,5,b],\
[b,b,b,3,6,b,0,2,7],\
[b,b,b,b,9,5,2,0,4],\
[b,b,b,b,b,b,7,4,0]]
P=[[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],\
[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],\
[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
D=[[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],\
[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],\
[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
def Floyd(G,P,D):
t=0
for u in range(0,len(G)):
for s in range(0,len(G)):
D[u][s]=G[u][s]
P[u][s]=s
for k in range(0,len(G)):
for v in range(0,len(G)):
for w in range(0,len(G)):
if D[v][w]>D[v][k]+D[k][w]:
t=t+1
D[v][w]=D[v][k]+D[k][w]
P[v][w]=P[v][k]
Floyd(G, P, D)
def search(s,u):
lenth=D[s][u]
print("路徑長(zhǎng)度為",lenth)
f=P[s][u]
foot=[s,f]
if f==u:
print("無(wú)需規(guī)劃，0步")
while f!=u:
f=P[f][u]
foot.append(f)
for i in range(0,len(foot)):
if i==0:
print("起 點(diǎn)____",foot[i])
elif i==len(foot)-1:
print("終 點(diǎn)____",foot[i],"步長(zhǎng)___",G[foot[i-1]][foot[i]])
else:
print("第",i,"點(diǎn)____",foot[i],"步長(zhǎng)___",G[foot[i-1]][foot[i]])
print("鄰接矩陣")
for i in range(0,9):
print(G[i])
s=input("請(qǐng)輸入起點(diǎn)0-8\n")
u=input("請(qǐng)輸入終點(diǎn)0-8\n")
Floyd(G, P, D)
search(int(s),int(u))
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
就在前段時(shí)間，在大學(xué)睡我上鋪的兄弟，在兄嘚群里討論，說(shuō)：他發(fā)現(xiàn)女朋友這幾天只要下班就坐在電腦前，不是工作原因。而且只要他靠近一點(diǎn)就會(huì)立即退出頁(yè)面，所以他一直很懷疑，在群里問(wèn)我們這一個(gè)個(gè)單身狗。然后就出現(xiàn)下面這一段對(duì)話2021-10-10
Python中threading模塊join函數(shù)用法實(shí)例分析
這篇文章主要介紹了Python中threading模塊join函數(shù)用法,以實(shí)例形式較為詳細(xì)的分析了join函數(shù)的功能與使用方法,需要的朋友可以參考下2015-06-06
這篇文章主要給大家介紹了關(guān)于Python流程控制語(yǔ)句的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用Python具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06
Python DataFrame設(shè)置/更改列表字段/元素類型的方法
今天小編就為大家分享一篇Python DataFrame設(shè)置/更改列表字段/元素類型的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-06-06
掌握Python?Restful?接口測(cè)試,讓你的后端服務(wù)像流水一樣順暢,本指南將帶你輕松穿梭于斷言和請(qǐng)求之間,搞定所有測(cè)試難題,一起來(lái)看,讓代碼在你的指尖跳舞吧！2023-12-12
Python?OpenCV超詳細(xì)講解圖像堆疊的實(shí)現(xiàn)
OpenCV用C++語(yǔ)言編寫(xiě)，它具有C ++，Python，Java和MATLAB接口，并支持Windows，Linux，Android和Mac OS，OpenCV主要傾向于實(shí)時(shí)視覺(jué)應(yīng)用，并在可用時(shí)利用MMX和SSE指令，本篇文章帶你通過(guò)OpenCV實(shí)現(xiàn)圖像堆疊2022-04-04
python設(shè)置隨機(jī)種子實(shí)例講解
在本篇文章里小編給大家整理的是關(guān)于python設(shè)置隨機(jī)種子的相關(guān)知識(shí)點(diǎn)以及實(shí)例內(nèi)容，需要的朋友們學(xué)習(xí)下。2019-09-09
文件上傳服務(wù)器-jupyter 中python解壓及壓縮方式
這篇文章主要介紹了文件上傳服務(wù)器-jupyter 中python解壓及壓縮方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-04-04
Django數(shù)據(jù)庫(kù)遷移常見(jiàn)使用方法
這篇文章主要介紹了Django數(shù)據(jù)庫(kù)遷移常見(jiàn)使用方法,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11
TensorFlow2中提供的幾種處理特征列的方法小結(jié)
本文主要介紹了TensorFlow2中提供的幾種處理特征列的方法小結(jié),主要介紹了6種方式,具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09