基于Python实现迪杰斯特拉和弗洛伊德算法

2023-08-31 16:24:07 147

#encoding=UTF-8 MAX=9 ''' Createdon2016年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=[] defDjstela(G,P,D): final=[] foriinrange(0,len(G)): final.append(0) D.append(G[0][i]) P.append(0) D[0]=0 final[0]=1 k=0 forvinrange(1,len(G)): min=999 forwinrange(0,len(G)): iffinal[w]==0andD[w]

FLOYD算法

#encoding=UTF-8
'''
Createdon2016年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]]
defFloyd(G,P,D):
t=0
foruinrange(0,len(G)):
forsinrange(0,len(G)):
D[u][s]=G[u][s]
P[u][s]=s
forkinrange(0,len(G)):
forvinrange(0,len(G)):
forwinrange(0,len(G)):
ifD[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)
defsearch(s,u):
lenth=D[s][u]
print("路径长度为",lenth)
f=P[s][u]
foot=[s,f]
iff==u:
print("无需规划，0步")
whilef!=u:
f=P[f][u]
foot.append(f)
foriinrange(0,len(foot)):
ifi==0:
print("起点____",foot[i])
elifi==len(foot)-1:
print("终点____",foot[i],"步长___",G[foot[i-1]][foot[i]])
else:
print("第",i,"点____",foot[i],"步长___",G[foot[i-1]][foot[i]])
print("邻接矩阵")
foriinrange(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实现迪杰斯特拉和弗洛伊德算法

热门推荐

随机推荐