《算法图解》之狄克斯特拉算法

╰+哭是因爲堅強的太久メ 2022-11-05 00:47 177阅读 0赞

前言在学习广度优先搜索的时候，你找出了从A点到B点的路径。这是最短路径，因为段数最少——只有三段，但不一定是最快路径。如果给这些路段加上时间，你将发现有更快的路径。如果你要找出最快的路径，该如何办呢？为 ...

<table> 
 <tbody> 
 <tr> 
 <td> &nbsp; <h1>前言</h1> 在学习广度优先搜索的时候，你找出了从A点到B点的路径。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/064a4fa49c9f0303a23590eb1c81827b.png"> 这是最短路径，因为段数最少——只有三段，但不一定是最快路径。如果给这些路段加上时间，你将发现有更快的路径。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/ec2eb2695895600f87eb1109516c9427.png"> 如果你要找出最快的路径，该如何办呢？为此，可使用另一种算法——狄克斯特拉算法（Dijkstra’s algorithm）。 &nbsp; <h1>使用狄克斯特拉算法</h1> 下面来看看如何对下面的图使用这种算法。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/045c7e250d73405d890980a2d16d91e3.png"> 其中每个数字表示的都是时间，单位分钟。为找出从起点到终点耗时最短的路径，你将使用狄克斯特拉算法。 如果你使用广度优先搜索，将得到下面这条段数最少的路径。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/601d51ad9016f80c33444fdce4ecc6c9.png"> 这条路径耗时7分钟。下面来看看能否找到耗时更短的路径！狄克斯特拉算法包含4个步骤。 
 <ul> 
 <li>(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。</li> 
 <li>(2) 更新该节点的邻居的开销，其含义将稍后介绍。</li> 
 <li>(3) 重复这个过程，直到对图中的每个节点都这样做了。</li> 
 <li>(4) 计算最终路径。</li> 
 </ul> 第一步：找出最便宜的节点。 你站在起点，不知道该前往节点A还是前往节点B。前往这两个节点都要多长时间呢？ &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/b1eb98e09aede38d936d794485919e28.png"> 前往节点A需要6分钟，而前往节点B需要2分钟。至于前往其他节点，你还不知道需要多长时间。 由于你还不知道前往终点需要多长时间，因此你假设为无穷大（这样做的原因你马上就会明白）。节点B是最近的——2分钟就能达到。 第二步：计算经节点B前往其各个邻居所需的时间。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/d03d14394b85504134af7cb9025485a6.png"> 你刚找到了一条前往节点A的更短路径！直接前往节点A需要6分钟。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/8380b9a7d7ce7a9405f1b6f958583c53.png"> 但经由节点B前往节点A只需5分钟！ &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/b149ee0545255e518a86200e5570bc64.png"> 对于节点B的邻居，如果找到前往它的更短路径，就更新其开销。在这里，你找到了： 
 <ul> 
 <li>前往节点A的更短路径（时间从6分钟缩短到5分钟）；</li> 
 <li>前往终点的更短路径（时间从无穷大缩短到7分钟）。</li> 
 </ul> 第三步：重复！ 重复第一步：找出可在最短时间内前往的节点。你对节点B执行了第二步，除节点B外，可在最短时间内前往的节点是节点A。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/d9c7c522aa18583270028ef613068877.png"> 重复第二步：更新节点A的所有邻居的开销。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/286c39a7718de36cdc8b3f0a391b26f6.png"> 你发现前往终点的时间为6分钟！ 你对每个节点都运行了狄克斯特拉算法（无需对终点这样做）。现在，你知道： 
 <ul> 
 <li>前往节点B需要2分钟；</li> 
 <li>前往节点A需要5分钟；</li> 
 <li>前往终点需要6分钟。</li> 
 </ul> &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/64747ae07ccf5dafcd795d4030c5edbe.png"> 最后一步——计算最终路径将留到下一节去介绍，这里先直接将最终路径告诉你。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/ff0ea72b0e9cfec497c003b2e9ec2c37.png"> 如果使用广度优先搜索，找到的最短路径将不是这条，因为这条路径包含3段，而有一条从起点到终点的路径只有两段。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/cce095a1368493f4fa27d98da97cd6d7.png"> 在前一章，你使用了广度优先搜索来查找两点之间的最短路径，那时“最短路径”的意思是段数最少。在狄克斯特拉算法中，你给每段都分配了一个数字或权重，因此狄克斯特拉算法找出的是总权重最小的路径。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/ba202d83400dd50930772061bc5952b0.png"> 这里重述一下，狄克斯特拉算法包含4个步骤。 
 <ul> 
 <li>(1) 找出最便宜的节点，即可在最短时间内前往的节点。</li> 
 <li>(2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。</li> 
 <li>(3) 重复这个过程，直到对图中的每个节点都这样做了。</li> 
 <li>(4) 计算最终路径。</li> 
 </ul> 实现 注意： 
 <ul> 
 <li>狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重（weight）。</li> 
 <li>如果有负权边，就不能使用狄克斯特拉算法。</li> 
 </ul> 下面来看看如何使用代码来实现狄克斯特拉算法，这里以下面的图为例。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/dc06d92c9a7e581f19dab72d39f0e1dc.png"> 要编写解决这个问题的代码，需要三个散列表。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/f5ec7c1a6004b9a45300fc726dc79084.png"> 随着算法的进行，你将不断更新散列表costs和parents。首先，需要实现这个图，为此可使用一个散列表。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/0ac4c95672b46570c6c4a384e6e04cea.png"> 在前一章中，你像下面这样将节点的所有邻居都存储在散列表中。 graph[“you”] = [“alice”, “bob”, “claire”] 但这里需要同时存储邻居和前往邻居的开销。例如，起点有两个邻居——A和B。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/2295db5f81a4ef0f38ed223367f969eb.png"> 如何表示这些边的权重呢？为何不使用另一个散列表呢？ &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/efcb4888c44fbff09ee5c3be1505c2e2.png"> &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/304ac11c93c0b7b7f07fc37ba3fec6ea.png"> 因此graph[“start”]是一个散列表。要获取起点的所有邻居，可像下面这样做。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/05d1f07a3051b63476c3d9307a248b53.png"> 有一条从起点到A的边，还有一条从起点到B的边。要获悉这些边的权重，该如何办呢？ &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/9e3c65e484543ac1aa37378b1b3a6aae.png"> 下面来添加其他节点及其邻居。 graph[“a”] = {} graph[“a”][“fin”] = 1 graph[“b”] = {} graph[“b”][“a”] = 3 graph[“b”][“fin”] = 5 #终点没有任何邻居 graph[“fin”] = {} 表示整个图的散列表类似于下面这样。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/52530779639101b9f84d55430eb605a3.png"> 接下来，需要用一个散列表来存储每个节点的开销。 节点的开销指的是从起点出发前往该节点需要多长时间。你知道的，从起点到节点B需要2分钟，从起点到节点A需要6分钟（但你可能会找到所需时间更短的路径）。你不知道到终点需要多长时间。对于还不知道的开销，你将其设置为无穷大。在Python中能够表示无穷大吗？你可以这样做： infinity = float(“inf”) 创建开销表的代码如下： infinity = float(“inf”) costs = {} costs[“a”] = 6 costs[“b”] = 2 costs[“fin”] = infinity 还需要一个存储父节点的散列表： &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/7e3f823807c6e1662fd78ef5f1b55218.png"> 创建这个散列表的代码如下： parents = {} parents[“a”] = “start” parents[“b”] = “start” parents[“fin”] = None 最后，你需要一个数组，用于记录处理过的节点，因为对于同一个节点，你不用处理多次。 processed = [] 准备工作做好了，下面来看看算法。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/6f184ca2bdf76d26e007061df872a794.png"> 我先列出代码，然后再详细介绍。代码如下。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/1144bb82667ef20c83b66abc570d8986.png"> 这就是实现狄克斯特拉算法的Python代码！函数find_lowest_cost_node的代码稍后列 出，我们先来看看这些代码的执行过程。 找出开销最低的节点。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/3a85b9017894a15a74bfd62d0b8a668e.png"> 获取该节点的开销和邻居。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/9c2339601e7affff03fd83bc18c0c318.png"> 遍历邻居。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/11d291ea0c349d7513da1c9a62a421c6.png"> 每个节点都有开销。开销指的是从起点前往该节点需要多长时间。在这里，你计算从起点出发，经节点B前往节点A（而不是直接前往节点A）需要多长时间。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/2cbe771e521510f4bf43b961b9b377e4.png"> 接下来对新旧开销进行比较。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/4ed489c67f5b78b20247bdeea616dde0.png"> 找到了一条前往节点A的更短路径！因此更新节点A的开销。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/2068fea176c0497693c83011670e7bbd.png"> 这条新路径经由节点B，因此节点A的父节点改为节点B。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/dfc178c75ba1c77c15721091c7ca450c.png"> 现在回到了for循环开头。下一个邻居是终点节点。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/1a48a9d4f01732a8c6efa81a3d946230.png"> 经节点B前往终点需要多长时间呢？ &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/8eaf578a39b22a455cc02280c1a9b2b4.png"> 需要7分钟。终点原来的开销为无穷大，比7分钟长。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/6b458c257146be16e46e969edb775522.png"> 设置终点节点的开销和父节点。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/0a69914d4c61a5dce43dedd78ea53c0b.png"> 你更新了节点B的所有邻居的开销。现在，将节点B标记为处理过。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/802febf76d8c4eb11675d17e1d9bff5b.png"> 找出接下来要处理的节点。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/d3042537868326546a9a4ced129a6dff.png"> 获取节点A的开销和邻居。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/4f950a5d9f9a793c63d985d4ee0ccb4b.png"> 节点A只有一个邻居：终点节点。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/8ff53e01e7370697021e18c2b7dfe5e6.png"> 当前，前往终点需要7分钟。如果经节点A前往终点，需要多长时间呢？ &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/201504a5f9a5a063be52d554c05f1925.png"> 经节点A前往终点所需的时间更短！因此更新终点的开销和父节点。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/dbefe26922b91135cd74ac02e4e5a71a.png"> 处理所有的节点后，这个算法就结束了。希望前面对执行过程的详细介绍让你对这个算法有更深入的认识。函数find_lowest_cost_node找出开销最低的节点，其代码非常简单，如下所示。 &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/77febc32d12d4c1185ee40915be34edb.png"> 完整代码如下： &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/4840b754cd3d695a4fd11f005bb69eb3.png"> &nbsp; <img alt="《算法图解》之狄克斯特拉算法" src="https://img-blog.csdnimg.cn/img_convert/598af9433412ef43059c4209d65f8556.png"> &nbsp; </td> 
 </tr> 
 </tbody> 
</table>