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基础教程

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。