巴尔加瓦算法图解——第七章 狄克斯特拉算法

第七章?狄克斯特拉算法

目录

第七章?狄克斯特拉算法

7.1　使用狄克斯特拉算法

7.2　术语

7.3　换钢琴

7.4?负权边

7.5　用代码实现

7.6　小结

---

??继续图的讨论，介绍加权图——提高或降低某些边的权重。

??介绍狄克斯特拉算法，让你能够找出加权图中前往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　小结

??广度优先搜索用于在非加权图中查找最短路径。

??狄克斯特拉算法用于在加权图中查找最短路径。

??仅当权重为正时狄克斯特拉算法才管用。

??如果图中包含负权边，请使用贝尔曼-福德算法。

【有没有发现我现在的笔记更加精简了？因为我发现直接上手对程序的处理是更加迅速有效的学知识的办法。】