07-狄克斯特拉算法

数据结构和算法
基于《算法图解》—Aditya Bhargava 和《数据结构》—严蔚敏

第7章 狄克斯特拉算法

上一章的广度优先搜索，找出的是段数最少的路径；
本章狄克斯特拉算法，找出的是最快的路径。

7.1 使用狄克斯特拉算法
步骤：
第一步：找出最便宜的节点

从起点出发，前往节点A需要6分钟，而前往节点B需要2分钟。置于前往其他节点，先假设为不穷大。

第二步：计算经节点B前往其各个邻居所需的时间。

经节点B可以找到前往节点A更短的路径，只需要5分钟。

对于节点B的邻居，如果找到前往它的更短路径，就更新其开销：

• 前往节点A的更短路径(从6分钟缩短到5分钟)。
• 前往终点的更短路径(从无穷大缩短到7分钟)。

第三步：重复

重复第一步：找出可能在最短时间内前往的节点。 已经对节点B执行了第二步，除节点B外，可在最短时间内前往的节点是节点A。

重复第二步：更新节点A的所有邻居节点开销。

可以发现前往终点的时间为6分钟。

7.1.1
使用广度优先搜索来查找两点之间的最短路径，指的是段数最少；
而在狄克斯特拉算法中，每段都分配了一个数字或权重，因此找出的是总权重最小的路径。

狄克斯特拉算法的4个步骤：

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

7.2 术语

• 狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重(weight)。
• 带权重的图为加权图(weighted graph)，不带权重的图为非加权图(unweight graph)。
• 环：从一个节点出发，走一圈后又回到这个节点。绕环的路径不可能是最短路径。
• 无向图意味着两个节点彼此指向对方，其实就是环。在无向图中，每条边都是一个环。
• 狄克斯特拉算法只适用于有向无环图(directed acyclic graph，DAG)。

7.3 换钢琴例子
Rama想用自己的乐谱来换架钢琴，那么需要确定哪种路径将乐谱换成钢琴时需要支付的额外费用最少。

使用狄克斯特拉算法可得到：

7.4 负权边
如果有负权边，就不能使用狄克斯特拉算法。
因为狄克斯特拉算法是这样假设的：对于处理过的海报节点，没有前往该节点的更短路径。这种假设仅在没有负权边时才成立。
在包含负权边的图中，要找出最短路径，可使用贝尔曼-福德算法。

7.5 实现
以下图为例。

要编写解决这个问题的代码，需要三个散列表。

算法实现思路

#实现图GRAPH：将节点的邻居和前往邻居的开销存储到散列表中。 graph["start"] = {} graph["start"]["a"] = 6 graph["start"]["b"] = 2graph["a"] = {} graph["a"]["fin"] = 1 #fin指到终点graph["b"] = {} graph["b"]["a"] = 3 graph["b"]["fin"] = 5graph["fin"] = {} #终点没有任何邻居#实现图COSTS：节点的开销指的是从节点出发前往该节点需要多长时间。 infinity = float("inf") costs = {} costs["a"] = 6 costs["b"] = 2 costs["fin"] = infinity#实现图PARENTS：存储父节点的散列表。 parents = {} parents["a"] = "start" parents["b"] = "start" parents["fin"] = None processed = [] #记录处理过的几点的数组，避免多次处理。

准备工作做好了，接下来实现算法。
图4.2

#首先定义函数find_lowest_cost_node找出开销最低的结点 def find_lowest_cost_node(costs):lowest_cost = float("inf")lowest_cost_node = Nonefor node in costs: #遍历所有节点cost = costs[node]if cost < lowest_cost and node not in processed: #如多当前节点的开销更低且未处理过，lowest_cost = cost #就将其视为开销最低的节点lowest_cost_node nodereturn lowest_cost_node#实现狄克斯特拉算法 node = find_lowest_cost_node(costs) #在未处理的节点中找出开销最小的节点。 while node is not None: #这个while循环在所有节点都被处理过后结束cost = cost[node]neighbors = graph[node]for n in neighbors.key(s): #遍历当前节点的所有邻居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) #找出接下来要处理的节点，并循环

7.6 小结

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

——持续修改完善中…

总结

以上是生活随笔为你收集整理的07-狄克斯特拉算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。