运行迪杰斯特拉算法

Question

给定这样一张图：

         A
        ^ ^
       /   \
      3     4
     /       \
    B -- 5 -> C

E={(B,A)(C,A)(B,C)}

如果我们在节点 A 上运行 Dijkstra 会怎样？

A 初始化为 0，B 和 C 初始化为无穷大，但 A 没有指向任何地方。

那我们在B和C中随机选择？或者算法在那种情况下不起作用？

谢谢！

Answer 1

Dijkstra 仍会运行并为您提供此图的正确答案。如果你这样选择，你可以只用起始节点初始化队列，并在你探索它们时添加或更新邻居 to/in 队列。在这种情况下，算法将在从队列中提取 (A) 并探索其零邻居的一次迭代后终止，适当地使到 B 和 C 的距离为无穷大（没有前一个节点）并使 A 的路径为零。如果您考虑一下，这就是所需的答案，因为没有从 A 到 B 或 C 的路径。

或者，如果您像 Wikipedia 那样实现它，在开始时将每个节点添加到队列中，它仍然会产生相同的结果。

1  function Dijkstra(Graph, source):
2      dist[source] ← 0                           // Initialization
3
4      create vertex priority queue Q
5
6      for each vertex v in Graph:          
7          if v ≠ source
8              dist[v] ← INFINITY                 // Unknown distance from source to v
9              prev[v] ← UNDEFINED                // Predecessor of v
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                      // The main loop
15         u ← Q.extract_min()                    // Remove and return best vertex
16         for each neighbor v of u:              // only v that are still in Q
17             alt ← dist[u] + length(u, v)
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist, prev

提取 A 并探索它不存在的邻居后，没有任何更新。然后它将在 B 和 C 之间任意选择以提取下一个，因为它们具有相同的距离（当然不是 'randomly'，仅取决于您如何从队列中 initialize/extract）。

当它检查 B 时，它会看到它可以在 Infinity + 5 中到达 C，并不比当前到 C of Infinity 的距离好多少，所以没有更新，并且在 Infinity + 3 中到达 A，不比 A 的好当前距离 0.

当它检查 C 时，它会看到它可以在 Infinity + 4 中到达 A，不比当前到 A 的距离 0 好，所以没有更新。

然后队列为空，返回dist[A] = 0, dist[B] = dist[C] = Infinity相同的结果。

因此 Dijkstra 的正确实现将能够处理这样的图（就像任何具有非负权重的有向图一样）。

运行迪杰斯特拉算法

Running Dijkstra Algorithm

algorithm

graph

dijkstra

运行 迪杰斯特拉算法

Running Dijkstra Algorithm

algorithm

graph

dijkstra

运行迪杰斯特拉算法