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电脑。