Dijkstra algorithm python

Question

I'm trying to implement Dijkstra's algorithm in Python and something doesn't work. I think there is a problem somewhere and I cannot find it. Here's my code:

def Dijkstra(self, start, end, visited=[], distances = {}, predecessors = {}):
        allV = self.__repo.read_first_line()
        verteces = allV[0]
        if start == end:
        # We build the shortest path and display it
            path=[]
            pred=end
            while pred != None:
                path.append(pred)
                pred=predecessors.get(pred,None)
            path.reverse()
            print('Shortest path: '+str(path)+ " - " + "Cost = "+str(distances[start])) 
        else :     
            if not visited: 
                distances[start]=0
                # visit the neighbors
                neighbours = self.__repo.get_neighbours(start)
                for neighbor in neighbours :
                    if neighbor not in visited:
                        new_distance = distances[start] + self.get_cost(start, neighbor)
                        if new_distance < distances.get(neighbor,float('inf')):
                            distances[neighbor] = new_distance
                            predecessors[neighbor] = start
            # mark as visited
            visited.append(start)
        # now that all neighbors have been visited: recurse                         
        # select the non visited node with lowest distance 'x'
        # run Dijskstra with start='x'
            unvisited={}
            for k in range(1,int(verteces) + 1):
                if k not in visited:
                    unvisited[k] = distances.get(k,float('inf'))  
            x=min(unvisited, key=unvisited.get)
            self.Dijkstra(x,end,visited,distances,predecessors)

Answer 1

There are far simpler ways to implement Dijkstra's algorithm.

You can think of it as the same as a BFS, except:

1. Instead of a queue, you use a min-priority queue.
2. We only considered a node 'visited', after we have found the minimum cost path to it.

Please see below a python implementation with comments:

The example inputs is taken from this youtube Dijkstra's algorithm tutorial

import heapq

graph = {
    'A': {'B': 20, 'D': 80, 'G': 90},
    'B': {'F': 10},
    'F': {'C': 10, 'D': 40},
    'C': {'F': 50, 'D': 10, 'H': 20},
    'D': {'G': 20, 'C': 10},
    'H': {},
    'G': {'A': 20},
    'E': {'B': 50, 'G': 30}
}


def dijkstra(graph, source):
    priority_queue = []
    # The cost is 0, because the distance between source to itself is 0
    heapq.heappush(priority_queue, (0, source))
    visited = {}
    # basically the same as a normal BFS
    while priority_queue:
        # dequeue from the priority queue
        # dequeue the minimum cost path
        (current_distance, current) = heapq.heappop(priority_queue)

        # When we extract min from the priority queue
        # we know that we have found the minimum cost path to this node
        # so we consider it visited
        visited[current] = current_distance

        if current not in graph: continue
        for neighbour, distance in graph[current].items():
            # We only continue to explore neighbours that have been visited
            # (same as a normal BFS)
            if neighbour in visited: continue
            # If we haven't found the min cost path to this node, we push the new distance back onto the queue
            # because this is a min queue, if the new distance is the new min cost path, it will be at the front of the queue
            new_distance = current_distance + distance
            heapq.heappush(priority_queue, (new_distance, neighbour))

    return visited

print dijkstra(graph, 'A')
# {'A': 0, 'C': 40, 'B': 20, 'D': 80, 'G': 90, 'F': 30, 'H': 60}

P.S. Ideally, you would use a priority queue dictionary where you can decrease the priority on existing nodes. This will decrease memory usage and time.

However, a normal heap queue will give you the same level of correctness, because if we find a new min cost path, it will get put into the front of the queue.

And when we get to the older items with higher costs, those nodes would have already been processed and therefore does not impact the output