您好,登錄后才能下訂單哦!
這篇文章主要為大家展示了基于Python如何實現Djstela和FLOYD算法,內容簡而易懂,希望大家可以學習一下,學習完之后肯定會有收獲的,下面讓小編帶大家一起來看看吧。
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))
以上就是關于基于Python如何實現Djstela和FLOYD算法的內容,如果你們有學習到知識或者技能,可以把它分享出去讓更多的人看到。
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。