python最短路径算法如何选择

说明

1、解决任意两个节点之间的最短距离，用Floyd。

2、解决单源最短路径问题，有负边时用Bellman-Ford，无负边时用Dijkstra。

3、A*算法找到了相对路径，适用于大规模、高实时性的问题。

实例

#!/usr/bin/python3
#coding=utf-8
my_max=0xffff


defDijkstra(v,G,d,vis,n):
#自身到自身为0
d[v]=0
foriinrange(n):
u=-1
my_min=my_max
forjinrange(n):
ifvis[j]==Falseandd[j]<my_min:
u,my_min=j,d[j]
ifu==-1:
return
vis[u]=True
forsinrange(n):
ifvis[s]==FalseandG[u][s]!=my_maxandd[u]+G[u][s]<d[s]:
d[s]=d[u]+G[u][s]


defmian():
n,edges,v=map(int,input('请输入图的节点个数,边个数和起始点:').split())
#n=3
#edges=3
d=[my_maxfortinrange(n)]
vis=[Falseforiinrange(n)]
G=[]
#G=[[my_max,1,my_max],[1,my_max,3],[my_max,3,my_max]]
forjinrange(n):
G.append([my_maxfortinrange(n)])
foriinrange(edges):
node1,node2,edge_node=map(int,input('请输入请输入两个节点和中间的边:').split())
G[node1][node2]=edge_node
G[node2][node1]=edge_node

Dijkstra(v,G,d,vis,n)
foriinrange(len(d)):
print('节点%d到节点%d的最短距离是：%d'%(v,i,d[i]))


if__name__=='__main__':
mian()

以上就是python最短路径算法的选择方法，希望对大家有所帮助。更多Python学习指路：python基础教程

本文教程操作环境：windows7系统、Python 3.9.1，DELL G3电脑。

课程教程：python最短路径算法如何选择

内容版权声明：除非注明，否则皆为本站转载文章。文章及图片版权归原作者所有，如有侵权请联系我们，我们立刻删除。