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

 #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]

 #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("无需规划，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))