算法集锦

算法集锦之路径规划算法(2):Dijkstra算法

 
 
AMadmin的头像
算法集锦之路径规划算法(2):Dijkstra算法
AMadmin 发表于 2017年08月13日 星期日 11:06
 

Dijkstra算法是一种用于查找图中节点之间的最短路径的算法,例如道路网络中寻找两点间的最短路径。它是计算机科学家Edsger W. Dijkstra在1956年提出的。


Dijkstra算法有很多应用,
原始算法是用于发现两个节点之间的最短路径,但一个更常见的变种将单个节点固定为源节点,并且找到从源到图中所有其他节点的最短路径,从而产生最短路径树

对于给定的一个源节点,该算法可以找到该节点与其他所有节点之间的最短路径。实际应用中,往往被用来寻找某节点到某个特定的目标节点之间的最短路径:只要发现源节点到目标节点之间的最短路径已经被确认,算法就可以停止运行。例如,如果图的节点代表城市,两个节点之间某条边代表连接这两个城市的道路,边的长度代表驾驶距离,则可以使用Dijkstra算法来找到一个城市和所有其他城市之间的最短路线。除此以外,Dijkstra算法也被广泛应用于其他方面,诸如网络链接中路由选择等。在人工智能领域,Dijkstra算法或其变种被称为统一成本搜索,最佳搜索思想的实例。



图1 Dijkstra算法演示(发呆专用图)


Dijkstra算法基本思路如下:


考虑一个图,该图由两部分组成:节点和连接结点的边。其中每条边还被指定了一个数值,表示从该边的一个端点移动到另一端点的代价,通常指距离。

让我们把图中的开始节点称为初始节点。让节点Y的距离是从初始节点到Y的距离。Dijkstra的算法将分配一些初始距离值,并尝试逐步改进。


  1. 为每个节点分配一个暂时的距离值:为我们的初始节点设置为零,对所有其他节点设置为无穷大。

  2. 将初始节点设置为当前节点。标记所有其他节点为未访问节点,创建一组称为未访问集的未访问节点。

  3. 对于当前节点,考虑其所有邻居并计算其临时距离。将新计算的临时距离与当前分配的值进行比较,并分配较小的值。例如,如果当前节点A的距离为6,并且与邻居B连接的边的长度为2,则到B(途径A)的距离将为 6 + 2 = 8,如果B先前标记的距离大于8,然后将其更改为8。否则,保持当前值。

  4. 当我们完成考虑当前节点的所有邻居时,将当前节点标记为已访问,并将其从未访问集中移除,以后将不会再次检查被访问的节点。

  5. 如果目标节点已被标记为访问(在两个特定节点之间规划路由时),或者未访问集合中的节点之间的最小暂定距离都是无穷远(当完整遍历时;当初始节点和剩余的未访问节点之间没有连接时)算法结束。

  6. 否则,选择标有最小暂定距离的未访问节点,将其设置为新的“当前节点”,然后返回到步骤3



点击下面的蓝色字体的阅读原文查看一个详细的例子。