4

我一直在尝试为以下无向图跟踪 Dijkstra 的最短路径算法：

        (乙)
       / \
      / \
  6 / \ 9
    / \
   / \
  / \
 (A)- 5 -(C)- 1 -(F)----2----(I)
   \ /
    \ /
  4 \ / 2
      \ /
       \ /
        \ /
         (四)

为了澄清：
(N) 代表节点，没有格式的数字代表权重。
A 和 C 之间的边的权重为 5，
C 和 F 之间的边的权重为 1。

我将在这里概述我的过程：

由于 A 是我的初始节点，因此算法从这里开始。由于 D 是更便宜的路径，算法会遍历 D。A 现在被标记为已访问，这意味着我们不能再次遍历它。

在 D 处，很容易看出我们将移至 F。

F是我开始遇到麻烦的地方。由于最短路径将引导我到 C，我被困在两个访问节点之间，无法到达 I。有人可以帮助我吗？

编辑：对不起图表家伙，这个问题最初是通过电话提出的。我会尽快修好。

4

4 回答 4

5

你的工作方式是错误的。“在 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，因为它在所有未访问的节点中成本最低。从那里你更新你到 I 的路径，它不再是 INFINITE 而是 8。

因此，您从 A 到 I 的最短路径如下： A - D - F - I 。

于 2012-07-26T23:17:29.413 回答
0

从C你仍然不能回到A，你不能回到F，所以这条路是假的。如果 C 给您带来死胡同，您需要在下一次迭代中从图中删除它，或者忽略最后一步并按照您的预期从 F 移动到 I。

于 2012-07-26T23:02:20.263 回答
0

http://en.wikipedia.org/wiki/Dijkstra 's_algorithm - 你记得它在移动到另一个顶点之前会处理一个顶点的所有邻居，对吧？在转到 D 之前，它会处理 C 和 B（计算它们的距离）。从你的图表来看，D和F之间没有路线..

于 2012-07-26T23:03:49.817 回答
0

Dijkstra 算法使用优先级队列。这不是图上的行走，并且可以按不类似于路径的顺序访问顶点。例如，这棵树：

A -> B -> C
  \
   > D -> E -> F

所有权重 1 按 A、B、D、C、E、F 的顺序进行探索。每次迭代都以最小的成本访问顶点并将其弹出；最初你弹出 A，B 和 D 的成本更新为 1；你访问 B，C 的成本更新为 2；你访问 D，E 的成本更新为 2；您访问 E；最后是 F。

于 2012-07-26T23:11:22.890 回答