Dijkstra的算法:为什么我最终会陷入这个例子？

Question

我一直试图追踪Dijkstra的最短路径算法,用于以下无向图:

        (B)
       /   \
      /     \
  6  /       \ 9
    /         \ 
   /           \
  /             \
 (A)- 5 -(C)- 1 -(F)----2----(I)
   \            /
    \          / 
  4  \        / 2
      \      /
       \    /
        \  /
         (D)

For clarification:
(N) will represent nodes, numbers with no formatting will represent weights.
the edge between A and C has a weight of 5, 
the edge between C and F has a weight of 1. 

我将在此概述我的流程:

由于A是我的初始节点,因此算法从这里开始.由于D是更便宜的路径,因此算法遍历到D.现在将A标记为已访问,这意味着我们无法再次遍历它.

在D,我们很容易看到我们将搬到F.

F是我开始遇到麻烦的地方.由于最短的路径将引导我到C,我被困在两个访问过的节点之间,没有办法到达我.任何人都可以帮助我吗？

编辑:抱歉图表的家伙,这个问题最初是从手机上询问的.我会尽快解决这个问题.

Answer 1

你正在努力的方式是错误的."在D处很容易看出我们将转向F",这是不正确的.你首先访问D,然后访问C,而不是F.仔细查看算法及其作用.

首先,您访问A,因此您有以下成本:6到B,5到C,4到D和其余节点的INFINITE.

你首先去D.你现在更新你的成本从A到F(通过D)到6.你的下一个访问节点不是D,它是C,因为它具有所有未访问的最低成本(5)节点.从A到F经过C的成本是6,这已经是您的成本,因此无需更新.

从那里你在B和F之间有一个6的关系.让我们说你先去B,然后没有任何事情发生,因为到F的最短路径已经是6,而通过B到F去将花费15,这是更昂贵的比你已经拥有的成本,所以不要更新成本.然后您访问F,因为它具有所有未访问节点的最低成本.从那里你更新你的路径,它不再是INFINITE而是8.

因此,从A到I的最短路径如下:A - D - F - I.