狄克斯拉特算法(Dijkstra)

今天看《算法图解》这本书,讲到狄克斯拉特算法(Dijkstra)。感觉挺有意思的,所以将书中的小例子用python代码实现,然后记录一下。

狄克斯拉特算法(Dijkstra)

首先,讲讲什么是狄克斯拉特算法。狄克斯拉特算法是解决从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。

那么什么是有权图呢?在将这个之前,我们先来讲什么是

image-20220524163113240

Alex欠Rama的钱,Tom欠Rama和Adit的钱,图由节点和边组成。一个节点可能与众多节点直接相连,这些节点被称为邻居。在前面的欠钱图中,Rama是Alex的邻居。Adit不是Alex的邻居,因为他们不直接相连。但Adit既是Rama的邻居,又是Tom的邻居。

加权图

那么加权图就是在每条边上都有权重的图。就像下面这个图片里标注的一样。去每个不同的节点所消耗的时间。

image-20220524162903455

算法具体步骤

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

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

步骤比较抽象,下面举个具体的例子。

例子

这是Rama,想拿一本乐谱换架钢琴。

Alex说:“这是我最喜欢的乐队Destroyer的海报,我愿意拿它换你的乐谱。如果你再加5美元,还可拿乐谱换我这张稀有的Rick Astley黑胶唱片。

”Amy说:“哇,我听说这张黑胶唱片里有首非常好听的歌曲,我愿意拿我的吉他和架子鼓换这张海报和黑胶唱片。”

Beethoven惊呼:“我一直想要吉他,我愿意拿我的钢琴换Amy的吉他或架子鼓。”太好了!只要再花一点点钱,Rama就能拿乐谱换架钢琴。

现在他需要确定的是,如何花最少的钱实现这个目标。我们来绘制一个图,列出大家的交换意愿。

image-20220524163841685

首先我们为上面的图建立数据模型,我们可以用python的字典存储上面的数据

# 图
graph = {}

graph['乐谱'] = {}
graph['乐谱']['海报'] = 0
graph['乐谱']['黑胶唱片'] = 5

graph['海报'] = {}
graph['海报']['吉他'] = 30
graph['海报']['架子鼓'] = 35

graph['黑胶唱片'] = {}
graph['黑胶唱片']['吉他'] = 15
graph['黑胶唱片']['架子鼓'] = 20

graph['吉他'] = {}
graph['吉他']['钢琴'] = 20

graph['架子鼓'] = {}
graph['架子鼓']['钢琴'] = 10

graph['钢琴'] = {}

我们再建立一个花费的字典,从乐谱开始,没有和乐谱直接相连的就是无穷远,和乐谱相连的就是相应的花费。

infinity = float("inf")  # 表示无穷
# 花费
costs = {}
costs['黑胶唱片'] = 5
costs['海报'] = 0
costs['吉他'] = infinity
costs['架子鼓'] = infinity
costs['钢琴'] = infinity

我们在建立一个父节点字典,后面我们要更新花费字典和父节点字典。

# 父节点
parents = {}
parents['海报'] = '乐谱'
parents['黑胶唱片'] = '乐谱'
parents['吉他'] = None
parents['架子鼓'] = None
parents['钢琴'] = None

再创建一个已处理的节点列表,防止重复处理

# 已处理过的节点
processed = []

上面的步骤中,第一步是:找出最便宜的节点。从乐谱开始,最便宜的节点就是海报了,不需要额外支出任何花费。我们来定义一个函数,可以从花费表里获取到最便宜的节点

# 找到未处理节点中,开销最小的节点
def find_lowest_cost_node(_costs):
    # 默认为无穷
    min_cost = infinity
    lowest_node = None
    for c in _costs:
        # 过滤已处理的
        if c not in processed:
            if _costs[c] < min_cost:
                min_cost = _costs[c]
                lowest_node = c
    return lowest_node

下一步就是获取最小节点邻居的节点,看看是否有通往他们花费最小的路径,有的话更新花费表和父节点表。然后重复这个过程,看最终代码

node = find_lowest_cost_node(costs)
while node is not None:
    cost = costs[node]
    # 获取邻居节点
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if new_cost < costs[n]:
            # 更新花销表和父节点表
            costs[n] = new_cost
            parents[n] = node
    # 处理完后加入到已处理过列表
    processed.append(node)
    # 找到未处理节点中,开销最小的节点
    node = find_lowest_cost_node(costs)

我们输出花销表和父节点表

print(costs)
print(parents)
{'黑胶唱片': 5, '海报': 0, '吉他': 20, '架子鼓': 25, '钢琴': 35}
{'海报': '乐谱', '黑胶唱片': '乐谱', '吉他': '黑胶唱片', '架子鼓': '黑胶唱片', '钢琴': '架子鼓'}

可以看到,兑换到钢琴,最低的花销是35。

路径可以从钢琴倒推回去,钢琴的父节点是架子鼓,架子鼓的父节点是黑胶唱片,以此循环,最终结果为:钢琴<-架子鼓<-黑胶唱片<-乐谱


狄克斯拉特算法(Dijkstra)
https://www.zhaojun.inkhttps://www.zhaojun.ink/archives/dijkstra
作者
卑微幻想家
发布于
2022-05-24
许可协议