基于Python實現(xiàn)迪杰斯特拉和弗洛伊德算法

更新時間：2020年05月27日 15:06:14 作者：BUAA-XX

這篇文章主要為大家詳細介紹了基于Python實現(xiàn)迪杰斯特拉和弗洛伊德算法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

圖搜索之基于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前一個選擇\n",P)
def search(x):
 print("選擇的終點",x,"最短路徑",D[x]) 
print("鄰接矩陣\n")
for i in range(0,9):
 print(G[i])
Djstela(G, P, D)
q=input("\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("路徑長度為",lenth)
 f=P[s][u]
 foot=[s,f]
 if f==u:
 print("無需規(guī)劃，0步")
 while f!=u:
 f=P[f][u] 
 foot.append(f) 
 for i in range(0,len(foot)):
 if i==0:
  print("起 點____",foot[i])
 elif i==len(foot)-1:
  print("終 點____",foot[i],"步長___",G[foot[i-1]][foot[i]])
 else:
  print("第",i,"點____",foot[i],"步長___",G[foot[i-1]][foot[i]])
print("鄰接矩陣")
for i in range(0,9):
 print(G[i])
s=input("請輸入起點0-8\n")
u=input("請輸入終點0-8\n")
Floyd(G, P, D)
search(int(s),int(u))

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: