Dijkstra的算法是否总是给出最短路径？ [英] Does Dijkstra's algorithm give shortest path always?

问题描述

我正在学习Dijkstra的算法，并进行了基本查询。我有一个如下图所示的图..（非负节点）：

I am learning Dijkstra's algorithm and had a basic query. I have a graph that looks as follows..(non-negative nodes):

A --- 2 ----- B ------ 16 ------ D ----- 3 ------- F

* *

* *

3 4

* *

C ---------- 2 ------------------------ --- E

A---2-----B------16------D-----3-------F
* *
* *
3 4
* *
C----------2---------------------------E

在上方的图形显示中不清楚，但是AC的距离为3，EF的距离为4。

Not clear from above graph display, but AC has a distance of 3 and EF has a distance of 4.

我有兴趣寻找A和F之间的最短路径。

I am interested in finding shortest path between A and F.

考虑目标节点F。当我们考虑它的最近节点时，得到D（DF权重3和EF 4）。但是，当我们沿着该路径行驶时，我们得到的最短路径为：A，B，D，F（总距离：19）。

Consider destination node F. When we consider its nearest node, we get D (DF has weight 3 and EF 4). However, when we follow that path, we get the shortest path as: A,B,D,F (total distance: 19).

快速观察告诉我们，最短路径实际上是A，C，E，F（距离：9）。但是，由于第一步中E比D更远，所以我们跟随D。

A quick observation tells us that the shortest path is actually A,C,E,F (distance: 9). However, since in the 1st step, E was more distant than D, we followed D.

我在这里错过了什么吗？ Dijkstra的算法显然无法在此处显示正确的结果。

Am I missing something here? Dijkstra's algorithm is clearly not showing the right result here.

推荐答案

是的，您缺少了一些东西。看看下面的第4步。

Yes, you are missing something. Have a look at step 4 below.

1. 第一步是将D的暂定距离标记为3，将E的暂定距离标记为4。 / li>
   
2. 下一步将选择D，因为它是暂定距离最小的未访问节点


3. 然后，您将标记D中所有未访问的节点与其距离（标记B的暂定距离为19（3 + 16））


4. 然后选择暂定距离最小的下一个未访问节点。这将选择E（4）


5. 标记所有E节点的暂定距离。 C标记为6（4 + 2）。


6. 然后选择暂定距离最小的下一个未访问节点。这将选择C（6）


7. 用暂定距离标记所有C的节点。 A标记为9（6 + 3）。

1. The first step would be to mark D with tentative distance 3 and E with tentative distance 4.
2. The next step would select D as it is the non visited node with the lowest tentative distance
3. Then you would mark all non-visited nodes from D with their distances (mark B with tentative distance 19 (3 + 16))
4. Then select the next non-visited node with the lowest tentative distance. This would select E (4)
5. Mark all of E's nodes with their tentative distance. C gets marked as 6 (4+2).
6. Then select the next non-visited node with the lowest tentative distance. This would select C (6)
7. Mark all of C's nodes with their tentative distance. A gets marked as 9 (6+3).

在到达A的距离为9时停止。

Stop as you have reach A with a distance of 9.

这篇关于Dijkstra的算法是否总是给出最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！