算法图解第7章笔记

发表于

标签： 笔记 简单算法 python

狄克斯特拉算法

要计算非加权图中的最短路径，可使用广度优先搜索。要计算 加权图中的最短路径，可使用狄克斯特拉算法。

实例分析：

在这张图上，你怎样用最少的钱将乐谱交换到钢琴？这时就要使用狄克斯特拉算法。

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

算法执行后更新的开销如下表：

从此，可以看出最低花销是35，如何将交换路线确定？只需从钢琴出发，不断求父节点直到乐谱为止就可以确定了。
补充：此算法不适用于负加权的图，若有负加权，应采用贝尔曼-福得算法（Bellman-Ford algorithm）。以后我会补充说明

代码实现狄克斯特拉算法

以上图为例，进行实现。
准备：
要构建两个散列表（costs&parents)和一个图（graph)。

  • costs散列表
    用来存储每个节点的开销，算法代码运行后会更新起点到该节点的最低花销。

    1
    2
    3
    4
    5
    6
    7
    #假设到达终点的花销为无穷大
    infinity=float("inf")
    #使用python的字典
    costs={}
    costs["a"]=6
    costs["b"]=2
    cost["fin"]=infinity

  • parents散列表
    存储各节点的父节点的散列表，算法代码运行后会更新起点到终点花销最低的路线（从终点不停找父节点直至起点）。

    1
    2
    3
    4
    5
    parents={}
    parents["a"]="start"
    parents["b"]="start"
    #将终点节点的父节点设为空
    parents["fin"]=None

  • graph图

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    graph={}
    graph["start"]={}
    graph["start"]["a"]=6
    graph["start"]["b"]=2
    graph["a"] = {}
    graph["a"]["fin"] = 1
    graph["b"] = {}
    graph["b"]["a"] = 3
    graph["b"]["fin"] = 5
    graph["fin"] = {}

    实现：

详细部分和思路请浏览第7章后半部分。

小结：

  • 广度优先搜索用于在非加权图中查找最短路径。
  • 狄克斯特拉算法用于在加权图中查找最短路径
  • 仅当权重为正时狄克斯特拉算法才管用。
  • 如果图中包含负权边，请使用贝尔曼-福德算法。