成都地铁建设分公司网站,博客 软件 wordpress,江门专业网站制作费用,seo营销推广费用本篇文章主要介绍了Dijkstra迪杰斯特拉算法的C实现#xff0c;文章包含两个部分#xff0c;在第一部分中我会简单介绍迪杰斯特拉算法以及一些个人的理解#xff0c;第二部分会对C代码的逻辑进行解释。下面是我已经上传的代码资源#xff0c;大家有兴趣的可以点击链接下载资…本篇文章主要介绍了Dijkstra迪杰斯特拉算法的C实现文章包含两个部分在第一部分中我会简单介绍迪杰斯特拉算法以及一些个人的理解第二部分会对C代码的逻辑进行解释。下面是我已经上传的代码资源大家有兴趣的可以点击链接下载资源。 迪杰斯特拉算法的C实现
迪杰斯特拉算法本质上是一个贪心算法通过不断迭代取得局部最优解的方法最终找到整体的最优解。迪杰斯特拉算法主要用于在有权图中计算出各节点到初始节点的最短路径。在接下来的分析中我会使用的有权图如下 : 其中ABCDE就是我们需要遍历的节点连接节点的弦上的数字表示了两节点之间的距离或称之为权重消耗。需要注意的几点是 :
迪杰斯特拉算法适用的有权图中节点之间的权重不要求是双向的即 A- B的权重和 B-A 的权重不要求相同。换而言之有权图中节点之间的连接可以是单向的或者在两个方向权重有所不同的。迪杰斯特拉算法适用的有权图中节点间连接的权重值不能是负值。
了解了迪杰斯特拉算法的一些注意点之后我们下面来重点解释算法的实现。之前我们已经提到了迪杰斯特拉算法多用于解决最短路径问题对应上述有权图就是计算出所有节点到初始节点的最短距离。在下述例子中我们默认使用A作为初始节点,目标就是找出所有节点到A的最短距离以及所经过的路径。 首先我们需要两个列表一个visited列表用于存放已经遍历过其所有邻节点的节点一个unvisited列表用于存放还未遍历过其所有邻节点的节点。我们会不断地进行迭代运算直到unvisited列表为空即所有的节点都已经访问过(遍历过其所有邻节点)。 显然初始状态visited列表为空[]unvisited列表中包含所有的节点[A,B,C,D,E]。 然后我们需要一个列表用于记录所有节点到A节点起始节点之间的最短距离以及最短路径中该节点之前的节点。 第一步初始化这个表格 : 显然A到A的距离为0其余节点到A的距离为未知初始化为正无穷。
节点节点到A的距离最短路径中该节点之前的节点A0B∞\infin∞C∞\infin∞D∞\infin∞E∞\infin∞
那么每一次迭代我们需要做的就是在unvisited列表中选择一个到A距离最短的节点并遍历更新其所有unvisited列表中的邻节点。 例如第一次迭代中unvisited未访问列表中A节点到A的最短距离最短那么我们首先就访问A所有unvisited的节点 B 和 D。简单来说如果通过A访问B比起之前的方式要距离更短那么我们就更新B到初始点的距离为新的最短距离并将B之前的节点更新为A。那么在这个例子中通过A访问B的距离为6通过A访问D的距离为1显然距离都比正无穷要小则更新列表如下 :
节点节点到A的距离最短路径中该节点之前的节点A0B6AC∞\infin∞D1AE∞\infin∞
同时更新visited列表以及unvisited列表: visited : [A] unvisited : [B,C,D,E]
既然未访问列表仍然不为空我们继续迭代选择D作为新的访问节点因为节点D目前到A的距离最短。那么节点D在unvisited列表中的邻节点有 B E那么我们更新BE的值和其原来的距离进行对比。 B : 12 3 6 \space E : 11 2 ∞\infin∞。 更新列表如下 :
节点节点到A的距离最短路径中该节点之前的节点A0B12 3DC∞\infin∞D1AE11 2D
同时更新visited列表以及unvisited列表: visited : [A,D] unvisited : [B,C,E] 我们继续迭代,方法同上。 访问E节点更新列表 :
节点节点到A的距离最短路径中该节点之前的节点A0B12 3DC115 7ED1AE11 2D
同时更新visited列表以及unvisited列表: visited : [A,D,E] unvisited : [B,C]
继续访问B更新列表 : B的唯一没有访问的邻节点为C但A … BC 的距离为 358 7因此C到节点A的距离不变。
节点节点到A的距离最短路径中该节点之前的节点A0B12 3DC115 7ED1AE11 2D
同时更新visited列表以及unvisited列表: visited : [A,D,E,B] unvisited : [C] 最后我们访问C列表不变因为C的所有邻节点都已经访问过了。 最终的结果如下 :
节点节点到A的距离最短路径中该节点之前的节点A0B3DC7ED1AE2D
通过迪杰斯特拉算法我们可以完备地遍历所有有权图中的节点并在最后返回一个所有节点到初始点的最短距离以及对应的最短路径的所有节点之前的节点。之后通过不断访问最短路径中该节点之前的节点我们就可以很简单地还原出最短路径。例如对节点C而言C之前的节点为EE之前的节点为DD之前的节点为A因此最短路径还原为A D E C。
参考 : [1] Graph Data Structure 4. Dijkstra’s Shortest Path Algorithm [2] (熟肉)Dijkstra算法详解轻松入门——Youtube
