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

Question

Me and my colleague are discussing a implementation of Dijkstra's algorithm. Here is the implementation using 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')

The controversial line here is:

if neighbor not in visited:

My point is that this line must be replaced with something like

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

In all the implementations that I found of the algorithm says that you must check for the case when you reach a node with a cost lower than the current cost of the node. For example, the lines 17 and 18 of this pseudocode from 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[]

The question is: Is my colleague's implementation correct or the code should be modified in order to check if you reach some neighbour with a price lower than the current one?

Note: Here is the source code of my colleague's implementation.

Answer 1

So, the question is whether the line in your code

if neighbor not in visited:

can or must be replaced by

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

The answer is: can, yes; must, no. Adding new_price < cost_so_far[neighbor] will not change anything in the flow of the algorithm, it will be false every time neighbor not in visited is false.

The reason is how Dijkstra's algorithm works. Essentially, it builds a tree of shortest paths. Whenever an airport is added to visited, it is considered to be in the tree: by this time, the algorithm has already found the shortest path to this airport.

Assume that at step x, we add a certain airport A to visited. Further assume that at step y > x, cost_so_far to airport A decreased. How could it decrease? It would require that some new_price = price + self.get_price(airport, neighbor) is less than the price at step y. Recall now that routes is a priority queue, so it supplies prices in non-decreasing order. The edges of the graph are also non-negative (otherwise, Dijkstra's algorithm indeed produces a wrong result and is not applicable). So, we arrive at a contradiction: the new new_price is at least the old price, but turned out to be less than that.

The source of confusion is perhaps that the main loop of the implementation considers some routes one-by-one. Essentially, these routes correspond to edges of the graph. So, there can be |E| routes, but only |V| of them will get accepted, all others will fail the condition if airport in visited: continue. If we implement the algorithm so that each iteration of the main loop adds exactly one airport to visited (exactly one vertex to the tree of shortest paths), the whole matter may become clearer.