巴尔加瓦算法图解——第七章 狄克斯特拉算法
第七章?狄克斯特拉算法
目录
??继续图的讨论，介绍加权图——提高或降低某些边的权重。
??介绍狄克斯特拉算法，让你能够找出加权图中前往X的最短路径。
??介绍图中的环，它导致狄克斯特拉算法不管用。
如果你要找出最快的路径（如第二个图所示），该如何办呢？为此，可使用另一种算法——狄克斯特拉算法(Dijkstra's algorithm)。
7.1 使用狄克斯特拉算法
狄克斯特拉算法包含4个步骤。(1)找出“最便宜”的节点，即可在最短时间内到达的节点。(2)更新该节点的邻居的开销，其含义将稍后介绍。(3)重复这个过程，直到对图中的每个节点都这样做了。(4)计算最终路径。
在狄克斯特拉算法中，你给每段都分配了一个数字或权重，因此狄克斯特拉算法找出的是总权重最小的路径
7.2 术语
狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重(weight)。
带权重的图称为加权图(weighted graph)，不带权重的图称为非加权图(unweighted graph)。
无向图=环
狄克斯特拉算法只适用于有向无环图(directed acyclic graph,DAG)。
7.3 换钢琴
最短路径指的并不一定是物理距离，也可能是让某种度量指标最小。
7.4?负权边
从黑胶唱片到海报的边的权重为负！即这种交换让Rama能够得到7美元。
第二种方式更划算——Rama可赚2美元。
如果有负权边，就不能使用狄克斯特拉算法。因为负权边会导致这种算法不管用。根据狄克斯特拉算法，没有比不支付任何费用获得海报更便宜的方式。
对于处理过的海报节点，没有前往该节点的更短路径。这种假设仅在没有负权边时才成立。因此，不能将狄克斯特拉算法用于包含负权边的图。在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼—福德算法(Bellman-Ford algorithm)。
7.5 用代码实现
from collections import defaultdict
def dijkstra(graph, start):
??? # 初始化节点的开销
??? costs = defaultdict(lambda: float('inf'))
??? costs[start] = 0
??? # 存储节点的父节点
??? parents = defaultdict(lambda: None)
??? # 记录已经处理过的节点
??? processed = set()
??? # 找到未处理节点中开销最小的节点
??? def find_lowest_cost_node():
??????? nonlocal costs, processed #引用上一层的局部变量
??????? lowest_cost = float('inf')
??????? lowest_cost_node = None
??????? for node, cost in costs.items():
??????????? if cost < lowest_cost and node not in processed: #检查当前节点开销
??????????????? lowest_cost = cost
??????????????? lowest_cost_node = node
??????? return lowest_cost_node
??? # 主循环
??? while True:
??????? node = find_lowest_cost_node()
??????? if node is None:
??????????? break
??????? cost = costs[node]
??????? neighbors = graph[node]
??????? # 更新邻居节点的开销和父节点
??????? for n, edge_cost in neighbors.items():
??????????? new_cost = cost + edge_cost
??????????? if new_cost < costs[n]:
??????????????? costs[n] = new_cost
??????????????? parents[n] = node
??????? # 将当前节点标记为已处理
??????? processed.add(node)
??? return costs, parents
# 示例图的定义
example_graph = {
??? 'A': {'B': 1, 'C': 4},
??? 'B': {'A': 1, 'C': 2, 'D': 5},
??? 'C': {'A': 4, 'B': 2, 'D': 1},
??? 'D': {'B': 5, 'C': 1}
}
# 从节点 'A' 开始运行 Dijkstra 算法
final_costs, final_parents = dijkstra(example_graph, 'A')
# 打印最终结果
print("Final Costs:", final_costs)
print("Final Parents:", final_parents)Final Costs: defaultdict(<function dijkstra.<locals>.<lambda> at 0x10a9c8ea0>, {'A': 0, 'B': 1, 'C': 3, 'D': 4})
Final Parents: defaultdict(<function dijkstra.<locals>.<lambda> at 0x10a9cb060>, {'B': 'A', 'C': 'B', 'D': 'C'})
7.6 小结
??广度优先搜索用于在非加权图中查找最短路径。
??狄克斯特拉算法用于在加权图中查找最短路径。
??仅当权重为正时狄克斯特拉算法才管用。
??如果图中包含负权边，请使用贝尔曼-福德算法。
【有没有发现我现在的笔记更加精简了？因为我发现直接上手对程序的处理是更加迅速有效的学知识的办法。】
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！