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

图搜索之基于python的迪杰斯特拉算法和弗洛伊德算法，供大家参考，具体内容如下

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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。