python算法----狄克斯特拉算法_迪斯科拉python算法

这次我们来学习一下图文结合的狄克斯特拉算法

狄克斯特拉算法包含4个步骤

(1) 找出最便宜的节点,即可在最短时间内前往的节点
(2) 对于该节点的邻居,检查是否有前往它们的更短路径,如果有,就更新其开销
(3) 重复这个过程,直到对图中的每个节点都这样做了
(4) 计算最终路径

术语:

狄克斯特拉算法用于每条边都有关联数字的图,这些数字称为权重(weight),带权重的图称为加权图(weighted graph),不带权重的图称为非加权图(unweighted graph)

计算非加权图的最短距离既可以用广度优先搜索,也可以用狄克斯特拉算法,但是有可能出现"环"的情况

在狄克斯特拉算法中,绕环的路径不可能是最短路径

狄克斯特拉算法只适用有向无环的图

最短路径指的并不一定是物理距离，也可能是让某种度量指标最小

负权边:

对有负权重的图使用狄克斯特拉算法,会错误的路径,因此.如果有负权边,就不能使用狄克斯特拉算法

在包含负权边的图中,要找出最短路径,可使用另一种算法——贝尔曼.福德算法(Bellman-Ford algorithm)

案例

找到从起点到终点的最小的开销

graph = {
   }      # 创建一个散列表

# 嵌套散列表去包含起点到各个的节点以及权重
graph["start"] = {
   }
graph["start"]["a"] = 6
graph["start"]["b"] = 
1
2
3
4
5
6
7