python - 使用 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]

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

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)小于 price在步骤y .现在回想一下 routes是一个优先队列，所以它提供 price s 非降序排列。图的边也是非负的(否则，Dijkstra算法确实会产生错误的结果，不适用)。所以，我们得出一个矛盾:新的 new_price至少是旧的价格，但结果却比那个低。

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