圖搜索之基于Python的迪杰斯特拉算法和弗洛伊德算法，供大家參考，具體內容如下

Djstela算法

#encoding=UTF-8MAX=9'''Created on 2016年9月28日@author: sx'''b=999G=[[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=0b=999G=[[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))

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林站長站。