理解狄克斯特拉算法:早上坐地铁最短用时多久就能到公司?

题目来源

灵感来自于《算法图解》第 7 章 「狄克斯特拉算法」,图片和代码也是来自该书。

题目描述

假设你住起点,公司在终点。坐地铁上班路线有三条,起点 -> A -> 终点起点 -> B -> A -> 终点起点 -> B -> 终点。请用狄克斯特拉算法,计算出早上坐地铁上班,最短用时多久就能到公司(不算换乘时间)?2 代表 20 分钟。路线图如下:

提示:可用三个散列表来表示各节点之间的关系:

  • GRAPH 表:记录所有节点到相邻节点(邻居)的时间
  • COSTS 表:记录起点到其他节点的时间(开销)
  • PARENTS 表:记录除起点以外的所有节点和其父节点(终点的父节点不确定)

解题方案

思路

  • 标签:狄克斯特拉算法哈希表
  • 狄克斯特拉算法:用于计算单源最短路径的算法
  • 从 COSTS 表中找出离起点用时最短(开销最低)的相邻节点(B)
  • 遍历 B 节点的邻居,如果起点经 B 到邻居的开销更低,更新 COSTS 表中此邻居的开销
  • 同时更新 PARENTS 表此邻居的父节点
  • 遍历完所有邻居后,将节点标记为已处理过
  • 继续从 COSTS 表中找出未被处理过的、离起点开销最低的节点,循环,直到所有节点都被处理过
  • 最终 COSTS 表中终点对应的值,就是结果
  • 时间复杂度:O (n^2^) (n 节点) * (n 邻居)

代码

# Python3
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 # ←------ fin -> finally

graph["fin"] = {} # ←------终点没有任何邻居

infinity = float("inf") # ←------表示无穷大
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None # ←------终点父节点不确定

processed = [] # ←------存放处理过的节点


def find_lowest_cost_node(costs):
lowest_cost = float("inf")
lowest_cost_node = None
for node in costs: # ←------遍历所有的节点
cost = costs[node]
if cost < lowest_cost and node not in processed: # ←------如果当前节点的开销更低且未处理过,
lowest_cost = cost # ←------就将其视为开销最低的节点
lowest_cost_node = node
return lowest_cost_node


node = find_lowest_cost_node(costs) # ←------找出离起点用时最短(开销最低)的相邻节点(B)
while node is not None: # ←------这个 while 循环在所有节点都被处理过后结束
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys(): # ←------遍历当前节点的所有邻居
new_cost = cost + neighbors[n]
if costs[n] > new_cost: # ←------如果经当前节点前往该邻居开销更低
costs[n] = new_cost # ←------就更新该邻居的开销
parents[n] = node # ←------同时将该邻居的父节点设置为当前节点
processed.append(node) # ←------将当前节点标记为处理过
node = find_lowest_cost_node(costs) # ←------找出接下来要处理的节点,并循环

print("早上用时最短到公司的时间:%s0 分钟" % costs['fin'])

图解

















思考

如果要问:「早上地铁坐那条路线耗时最短?」应该怎样修改代码?

DeppWang wechat
个人公众号