迪克斯特拉算法
2021/11/1 14:09:51
本文主要是介绍迪克斯特拉算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
参考:算法图解
# 在未处理的节点中找到开销最小的节点 def find_lowest_cost_node(costs, processed): lowest = float("inf") lowest_cost_node = None for node in costs: cost = costs[node] if cost < lowest and node not in processed: lowest = cost lowest_cost_node = node return lowest_cost_node def func(graph, costs, parents): processed = [] # 记录处理过的节点 node = find_lowest_cost_node(costs, processed) # 在未处理的节点中找到开销最小的节点 while node: cost = costs[node] neighbors = graph[node] for n in neighbors.keys(): # 更新到达邻居节点的花费 new_cost = cost + neighbors[n] if costs[n] > new_cost: costs[n] = new_cost parents[n] = node # 设置父节点 processed.append(node) node = find_lowest_cost_node(costs, processed) return costs["final"] if __name__ == '__main__': # graph dict # 记录每个节点的到邻居的花费 graph = {"start": {}, "a": {}, "b": {}, "final": {}} graph["start"]["a"] = 6 graph["start"]["b"] = 2 graph["a"]["final"] = 1 graph["b"]["a"] = 3 graph["b"]["final"] = 5 # cost dict # 记录到达每个节点的最小花费 infinity = float("inf") costs = {"a": 6, "b": 2, "final": infinity} # parents dict # 记录每个节点的前一个节点(花费最少) parents = {"a": "start", "b": "start", "final": None} print(func(graph, costs, parents))
这篇关于迪克斯特拉算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程