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)

Hello and welcome to Stack Overflow. Please note that "does not work" is a useless bug report; if it worked, you would not be asking about it. How specifically it doesn't work? Is there an error? What is it? If it is working but badly, what are the expected results and what is the actual behaviour? Providing test cases so your code can be quickly edited and tested is also a plus. — Amadan
– Amadan, Commented May 25, 2015 at 5:04
algorithm is independent to languages... If it does not work, you should figure out where is the problem, and if you can not solve it, you could ask here. It is a good chance to learn how to debug code. — Wingzero
– Wingzero, Commented May 25, 2015 at 5:04
Stop voting down guys, leave constructive comments instead. @laura, could you provide us your input and output plz? Thanks. — Toby D
– Toby D, Commented May 25, 2015 at 5:08
@TobyD Be happy to vote up if/when the question gets improved :) — James Mills
– James Mills, Commented May 25, 2015 at 5:19

samol · Accepted Answer · 2015-06-22 08:10:47Z

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

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

Instead of a queue, you use a min-priority queue.
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

Your algorithm doensn't work. https://www.hackerrank.com/challenges/dijkstrashortreach

Collectives™ on Stack Overflow

Dijkstra algorithm python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related