当前位置: 首页 > 编程笔记 >

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

乐华晖
2023-03-14
本文向大家介绍基于Python实现迪杰斯特拉和弗洛伊德算法,包括了基于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))

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持小牛知识库。

 类似资料:
  • 主要内容:弗洛伊德算法的实现思路,弗洛伊德算法的具体实现在一个加权图中,如果想找到各个顶点之间的最短路径,可以考虑使用弗洛伊德算法。 弗洛伊德算法既适用于无向加权图,也适用于有向加权图。使用弗洛伊德算法查找最短路径时,只允许环路的权值为负数,其它路径的权值必须为非负数,否则算法执行过程会出错。 弗洛伊德算法的实现思路 弗洛伊德算法是基于 动态规划算法实现的,接下来我们以在图 1 所示的有向加权图中查找各个顶点之间的最短路径为例,讲解弗洛伊德算法的实现思

  • 主要内容:迪杰斯特拉算法的实现思路,迪杰斯特拉算法的具体实现迪杰斯特拉算法用于查找图中某个顶点到其它所有顶点的最短路径,该算法既适用于无向加权图,也适用于有向加权图。 注意,使用迪杰斯特拉算法查找最短路径时,必须保证图中所有边的权值为非负数,否则查找过程很容易出错。 迪杰斯特拉算法的实现思路 图 1 是一个无向加权图,我们就以此图为例,给大家讲解迪杰斯特拉算法的实现思路。 图 1 无向加权图 假设用迪杰斯特拉算法查找从顶点 0 到其它顶点的最短路径,具体过

  • 弗洛伊德算法 弗洛伊德算法(Floyd-Warshall Algorithm),跟克鲁斯卡尔算法一样是为了解决给定加权图中某一个顶点到其他顶点间的最短距离,可以处理有向图或负权的最短路径问题,同时也被用于在计算有向图的传递闭关。该算法已创始人之一,1978年图领奖获得者,斯坦福大学计算机教授罗伯特·弗洛伊德。 适用范围:无负权回路即可,边权正负都可以,运行一次算法即可得到任意两点之间的最短路径。

  • 我在Kubernetes是个新手。我想知道在kubernetes环境中最好的生产部署场景是什么。 在过去的学派中,我习惯于将Web服务器(例如Nginx或Apache)放在DMZ层,而将其放在其他层(我们称之为层)。这样,只有web服务器在DMZ上,恶意攻击只能在web服务器VM上进行。 据我所知,K8S部署不再需要这种方法;这是因为K8S自己处理网络、吊舱和流量。所以我在考虑最确定的部署方案。

  • 迪杰斯特拉算法 迪杰斯特拉算法(Dijkstra)是经典的最短路径算法,用于计算一个节点到其他节点的最短路径。他的主要特点以起始点为中心向外层层扩散(广度优先搜索思想BFS),直到扩展到终点为止。 迪杰斯特拉算法过程 设置出发顶点为v,顶点集合V(v1,v2,v3…vn),v到V中其他顶点的距离构成一个集合Dis,Dis(d1,d2,d3…dn),记录着v到途中其他各个顶点的具体,v到v自身的距离

  • 本文向大家介绍C++用Dijkstra(迪杰斯特拉)算法求最短路径,包括了C++用Dijkstra(迪杰斯特拉)算法求最短路径的使用技巧和注意事项,需要的朋友参考一下 算法介绍 迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到