7 狄克斯特拉算法
名字比较绕，其实就是解决带权重图的最快路径问题——或者说是地图中的最快公交路线选择问题。
7.1 算法原理
如何选出最快路径
狄克斯特拉算法包含4个步骤。
(1) 找出最便宜的节点，即可在最短时间内前往的节点。
(2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。
s1
s2
以上图为例：
s1:从起点出发，可以前往两个点：A\B，到B最快-2，到A慢-6，到终点不确定,这一步确定最‘便宜’的点是B；
s2:对该节点的邻居，也就是B点的邻居——A点和终点，检查是否有前往其的更短路径：B到A是3，B到终点是5，那么起点经B点到A合计是5，比从起点直接到A点要快，更新起点到A点的开销，同理更新起点到终点的开销为6；
…
最终确定起点到终点的路径。
狄克斯特拉算法用来解决带权图的最短路径问题；广度优先算法解决最快步数问题（相当于无权图最短路径）
7.2 代码实现
解决7.1中的问题，需要三个散列表：一张用来存这张图，一张用来存‘开销’--也就是到达各点的路径长度，还有一张用来存储父节点（以便找到最终路径）
三张必要的散列表
图直接用一级一级的字典表示：
graph = {}
graph["you"] = ["alice", "bob", "claire"]
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"] = {} ←------终点没有任何邻居
创建开销表的代码如下：
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
创建父节点：
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
算法实现：
image.png
processed = [] ---- 避免多次处理同一个节点
node = find_lowest_cost_node(costs) ←------在未处理的节点中找出开销最小的节点
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) ←------找出接下来要处理的节点，并循环
网友评论