加权图的Dijkstra算法Python实现

---

在之前的讨论中，我们介绍了图形模型与广度优先搜索算法，并将其应用于解决'寻找关系者'的问题。当我们考虑将这一方法转化为寻找路径时，在从一个地点到另一个地点的情境下按照最短路径到达的情形下应用图形模型时会发现：连接——即两个地点之间的道路——具有长度属性；这种情况下传统的广度优先搜索算法就不再适用了——因为它仅能确保找到经过最少连接的数量而无法考虑道路长度的影响因素；接下来探讨如何在这种情况下找到最短路径的问题。

---

1. 两个术语

（1）.加权图

就像前面所述，在无权图中使用广度优先搜索是一种有效的方法；而在加权图中，则应采用狄克斯特拉算法来找到最短路径。在加权图中，每条边上的数值即为权重。

6

1

2

5

3

起点

A

终点

B

（2）.有向无环图

之前我们介绍过有向图和无向图，其实无向图就是一个环：

起点

终点

也就是无向意味着两个节点相互指向对方。

如果在一个图中存在一个环，并且该环的终点不在该环内时，则该循环将徒劳地增加权重。我们关注的重点是用于处理有向无环图（DAGs）的Dijkstra算法。

---

2. 狄克斯特拉算法

前面示例展示的那个图显得过于简单,不足以体现这个算法的所有细节.因此,在这里我们构建了一个更加复杂的图表,并对这一图表的实际意义进