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

yipeiwu_com5年前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))

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

Python浅拷贝与深拷贝用法实例

本文实例讲述了Python浅拷贝与深拷贝用法。分享给大家供大家参考。具体分析如下: >>> person=['name',['savings',100]] >...

jupyter安装小结

前段时间一直使用pycharm写pandas程序,对于大数据开发而言,开发一般是走一步想一步,pycharm不适合。网上推荐使用jupyter notebook,它是一个web版的编辑器...

Python猴子补丁知识点总结

属性在运行时的动态替换,叫做猴子补丁(Monkey Patch)。 为什么叫猴子补丁 属性的运行时替换和猴子也没什么关系,关于猴子补丁的由来网上查到两种说法: 1.这个词原来为Guerr...

python调用API实现智能回复机器人

本文实例为大家分享了python调用API实现机器人的具体代码,供大家参考,具体内容如下 注意事项: 下面代码中的APIKEY需要替换 需要有自己的公众号平台,并且自己成为管理员, h...

pandas 数据索引与选取的实现方法

我们对 DataFrame 进行选择,大抵从这三个层次考虑:行列、区域、单元格。 其对应使用的方法如下: 一. 行,列 --> df[] 二. 区域   --...