使用 Dijkstra 算法时是否必须检查多次访问的节点？

Question

我和我的同事正在讨论 Dijkstra 算法的实现。这是使用 Python 的实现：

def dijkstra(self, origin, destination):
        """Use Dijkstra's algorithm to find the cheapest path."""

        routes = Heap()
        for neighbor in self.neighbors(origin):
            price = self.get_price(origin, neighbor)
            routes.push(Route(price=price, path=[origin, neighbor]))

        visited = set()
        visited.add(origin)

        while routes:

            # Find the nearest yet-to-visit airport
            price, path = routes.pop()
            airport = path[-1]
            if airport in visited:
                continue

            # We have arrived! Wo-hoo!
            if airport is destination:
                return price, path

            # Tentative distances to all the unvisited neighbors
            for neighbor in self.neighbors(airport):
                if neighbor not in visited:
                    # Total spent so far plus the price of getting there
                    new_price = price + self.get_price(airport, neighbor)
                    new_path  = path  + [neighbor]
                    routes.push(Route(new_price, new_path))

            visited.add(airport)

        return float('infinity')

这里有争议的台词是：

if neighbor not in visited:

我的观点是，这一行必须替换为类似

的内容

if neighbor not in visited or new_price < cost_so_far[neighbor]

在我发现的算法的所有实现中，您必须检查到达成本低于节点当前成本的节点时的情况。例如，此伪代码的第 17 行和第 18 行 来自 Wikipedia:

1  function Dijkstra(Graph, source):
2      dist[source] ← 0                                    // Initialization
3
4      create vertex set 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 is 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[]

问题是：我同事的实现是正确的还是应该修改代码以检查您是否到达了价格低于当前价格的邻居？

注意：这里是我同事的实现source code。

Answer 1

所以，问题是你的代码中的行是否

if neighbor not in visited:

可以或必须替换为

if neighbor not in visited or new_price < cost_so_far[neighbor]:

答案是：可以，可以；必须，不。添加 new_price < cost_so_far[neighbor] 不会改变算法流程中的任何内容，每次 neighbor not in visited 为假时它都会为假。

原因在于 Dijkstra 算法的工作原理。本质上，它构建了一棵最短路径树。每当一个airport被添加到visited，它就被认为在树中：此时，算法已经找到了到这个airport.

的最短路径

假设在步骤x，我们将某个机场A添加到visited。进一步假设在 y > x 步，cost_so_far 到机场 A 减少。怎么会减少呢？它要求某些 new_price = price + self.get_price(airport, neighbor) 小于步骤 y 中的 price。现在回想一下 routes 是一个优先级队列，所以它以 non-decreasing 的顺序提供 prices。图的边也是non-negative（否则Dijkstra的算法确实会产生错误的结果，不适用）。所以，我们得出一个矛盾：新的 new_price 至少是旧的价格，但结果却低于旧的价格。

混淆的根源可能是实现的主循环考虑了一些路由 one-by-one。本质上，这些路线对应于图的边。所以，可以有 |E|路线，但只有 |V|其中一个将被接受，所有其他人将无法满足条件 if airport in visited: continue。如果我们实现算法，使得主循环的每次迭代恰好将airport添加到visited（恰好将一个顶点添加到最短路径树），整个事情可能会变得更清楚。

使用 Dijkstra 算法时是否必须检查多次访问的节点？

It's obligatory to check more than one time visited nodes when using Dijkstra's algorithm?

python

algorithm

dijkstra

shortest-path