大道之行,天下为公。这篇文章主要讲述[python] 狄克斯特拉算法相关的知识,希望能为你提供帮助。
狄克斯特拉算法
本人的理解
1.先以表格的形式整理坐标信息
(表格e 空白处为正无穷)
2.源点遇到的
第一批节点中
权重最小的节点 和 节点的权重
为确定值
(权重:大小,长度,时间长短,远近,这些量的数值)
3.在确定值的基础上"松弛"确定值节点的子类, 更新dis表
4.最近更新过的dis表中
取数值小的 作为下一个确定值
5.重复第4步操作 直至求出终点最短路径
dis表完成
文章图片
代码的实现(python)
文章图片
文章图片
【[python] 狄克斯特拉算法】
#迪克斯特拉算法
# (e表格)(坐标权重关系图的实现)
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
#print(graph)#{\'start\': {\'a\': 6, \'b\': 2}}
#print(graph["start"])#{\'a\': 6, \'b\': 2}
#print(graph["start"]["a"])#6
graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}#终点没有邻居
#汇总的坐标信息
#print(graph)
#开销表(算法图解中的名称)aka(我理解的叫法)(dis表,估计值表)(用来记录最短路径)
#定义无穷大
infinity = float("inf")
#创建开销表记录最小权重之和
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
#储存父节点的散列表
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
#避免重复处理
processed = []
#定义函数(查找costs中最小的值)
def find_lowest_cost_node(costs):
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost< lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node
#代码的实现
node = find_lowest_cost_node(costs)
while node is not None:
cost = costs[node]
neighbours = graph[node]
for n in neighbours.keys():
new_cost = cost + neighbours[n]
if costs[n] > new_cost:
costs[n]= new_cost
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs)
#最短路径
print(costs)
#{\'a\': 5, \'b\': 2, \'fin\': 6}
print(parents)
#{\'a\': \'b\', \'b\': \'start\', \'fin\': \'a\'}
推荐阅读
- linux中vi,vim操作技巧
- 面试官(MySQL 是如何执行一条查询语句的())
- 输入输出重定向
- Redis中的String类型16个常用方法(图文例子)
- java 从零开始手写 RPC (05) reflect 反射实现通用调用之服务端
- windows 10升级后出现网格图标显示一个地球状态
- 干货数据产品经理如何快速了解业务
- WP分类项的Single.php模板
- 如果page_id为3,则在页面上显示一些帖子,否则显示其他帖子