已确定
队列中
已检查的边

  • 当前
  • 队列中
  • 已确定
  • 路径
点击节点设为

更多关于 Dijkstra 算法

Dijkstra 算法

当边有长度时(比如城镇之间的道路),Dijkstra 算法能求出从起点到其他每个节点的最短路线。它从起点向外扩展,每次都取尚未完成的最近节点。点击节点从它出发,也可以选一个终点,然后逐步查看队列、每个距离随着更短的路线出现而下降,以及最短路径的出现。 按“播放”观看搜索过程,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。点击节点可将其设为起点;把点击切换为“终点”,再点击另一个节点,即可查找到它的最短路径。每条边上的数字是它的长度,每个节点上的数字是它目前的最短距离,图下方的一行是队列,最近的排在前面。“新图”会生成另一张图;可选择节点数和边数。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。

它是如何运作的

  1. 点击一个节点设为起点。要查找路径,把点击切换为“终点”,再点击另一个节点。
  2. 按“播放”,或用“单步”和“后退”一步一步移动。拖动步骤滑块可跳到搜索中的任意位置。
  3. 观察图下方的队列和每个节点上的距离。“新图”会生成另一张图供你尝试。

Dijkstra 算法的工作原理

起点的距离设为 0,其他每个节点设为无穷大,并把起点放入队列。然后重复:取出队列中距离最小的节点,把这个距离标记为已确定。对它的每个尚未确定的邻居,把边的长度加到该节点的距离上。如果和比邻居目前的距离短,它就成为新距离,该节点被记为通往那里的路线;邻居若不在队列中,就加入队列。队列为空时,每个可到达的节点都有了最短距离。

为什么最近的节点已确定

当一个节点是队列中最近的节点时,通往它的其他任何路线都必须经由队列中的某个节点离开图中已完成的部分,而那个节点至少同样远,之后再加上的边又不可能为负。所以没有别的路线能更短。这也是为什么终点要在从队列中取出时才确定,而不是第一次到达时;也是为什么 Dijkstra 算法遇到负权边会失败:这时需要 Bellman–Ford 算法。当每条边的长度都是 1 时,Dijkstra 算法和广度优先搜索做的事一样。

常见问题

什么是 Dijkstra 算法?

一种在边长为零或更大的图中,求出从一个起点到所有其他节点的最短路径的方法。它反复取出最近的未完成节点,确定它的距离,并用它的边缩短邻居的距离。

为什么 Dijkstra 算法不适用于负权边?

节点一成为队列中最近的节点,它的距离就被确定。之后发现的负权边仍可能通过更短的路线回到这个节点,因此确定的距离可能是错的。Bellman–Ford 算法能处理负权边,只要没有总和为负的环。

Dijkstra 和 BFS 有什么区别?

广度优先搜索数边的条数,使用普通队列。Dijkstra 算法把边长相加,使用总是给出最近节点的优先队列。如果每条边的长度都是 1,两者求出的距离相同。

Dijkstra 算法有多快?

用二叉堆作优先队列时,对于 V 个节点和 E 条边,工作量随 (V + E) log V 增长。用斐波那契堆时为 E + V log V。本应用把队列保存为有序列表,便于展示,对小图也足够。

我的图会被发送到别处吗?

不会。图在你的浏览器中生成和搜索,上次的设置保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器