python dijkstra 最短路算法示意代码
发布时间:2020-12-20 10:38:54 所属栏目:Python 来源:网络整理
导读:? def dijkstra(graph,from_node,to_node): q,seen = [(0,[])],set() while q: cost,node,path = heappop(q) seen.add(node) path = path+[node] if node == to_node: return cost,path for adj_node,c in graph.get(node,{}).items(): if adj_node not in s
? def dijkstra(graph,from_node,to_node): q,seen = [(0,[])],set() while q: cost,node,path = heappop(q) seen.add(node) path = path+[node] if node == to_node: return cost,path for adj_node,c in graph.get(node,{}).items(): if adj_node not in seen: heappush(q,(cost+c,adj_node,path)) return -1,[] air_lines = {"1":{"2":2000,"3":2000,"4":4000,"5": 4500},"2":{"5": 1000},"3":{"4": 1000},"4":{"5": 500}} print(dijkstra(air_lines,"1","4")) print(dijkstra(air_lines,"5")) print(dijkstra(air_lines,"4","5","1")) print(dijkstra(air_lines,"10","10")) """ (3000,[‘1‘,‘3‘,‘4‘]) (3000,‘2‘,‘5‘]) (500,[‘4‘,‘5‘]) (-1,[]) (0,[‘1‘]) (0,[‘10‘]) """ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |