dijkstra implementation in python - output is not always correct

Question

I made this implementation of dijkstra's algorithm of shortest paths with a priority dict based on heap. It has the following methods: smallest() - only returns the smallest key from the dict which has the smallest value. pop_smallest() returns the smallest key with the smallest value in the heap and also pops it from the heap dict. I tested the code on some tests on github and some tests are correct, some are not. I have seen many more implementations for this algo but i would want to make mine correct before i would see others which are better than mine.

I am a beginner, you may have the formed eye to identify what is wrong in my code. Kind regards, Edit: I don't know if i am allowed to post links to other websites but this website contains the tests i used: https://github.com/beaunus/stanford-algs/tree/master/testCases/course2/assignment2Dijkstra The context is that this implementation is part of an assignment for a coursera standford class about graphs. The assignment was to compute the distances to the 7'th node, 35'th node, etc). If some of these are wrong it is obvious something went wrong in the code. Just to be more clear , input_random_10_16 test outputs different answers. Not all the distances are correct.

My implementation outputs : [878, 405, 785, 534, 909, 328, 708, 957, 830, 911]
The correct answer is : [588, 405, 675, 521, 909, 328, 418, 957, 830, 839]

Some distances are correct, some are not.

EDIT: I finally remade a different implementation which passed all of the tests. This is the heap implementation. I also wanted to do the naive implementation which didn't use a heap. I searched online for different naive implementations and i found severall which output the same wrong results as this implementation. How is this possible? A good implementation also posted on github which worked for a lot of people when used on my graph outputed these wrong results.

def dijkstra(graph, s):
    processed = set([s])
    vertexes = set([])
    distances = {}
    ans = []
    heap = priority_dict()
    for i in graph:
        vertexes.add(i)
        distances[i] = 0
        if i not in processed:
            heap[i] = float('inf')
    while processed != vertexes:
        for i in processed:
            neigh = graph[i]
            for j in heap:
                if j in neigh:
                    score = distances[i] + graph[i][j]
                    if score < heap[j]:
                        heap[j] = score
        smallest_value = heap[heap.smallest()]
        smallest_key = heap.pop_smallest()
        processed.add(smallest_key)
        distances[smallest_key] = smallest_value
        for j in graph[smallest_key]:
            if j in heap:
                old_val = heap[j]
                new_val = min(old_val, distances[smallest_key] + graph[smallest_key][j])
                heap[j] = new_val
    list_ = [7,37,59,82,99,115,133,165,188,197]
    for i in list_:
        ans.append(distances[i])
    return ans

Please provide some examples of input, output and expected output (examples of where it fails). — Lomtrur
– Lomtrur, Commented May 7, 2018 at 9:09
Thank you for adding the outputs, but what are the associated inputs? And what is the object a in the calculation of the new distance? It doesn't seem to be defined anywhere — Martijn
– Martijn, Commented May 7, 2018 at 9:26
Sorry, I edited the code before posted it here and i missed some notations. The outputs refer the the distances from the source vertex to the 7'th node, 37'th node, 59'th node, to all the nodes in the list_ list in the bottom. It is obvious something is wrong in the code because some are correct, some are not. — georgeB
– georgeB, Commented May 7, 2018 at 9:29
A good idea in cases like this is looking for a smaller graph which also contains the same issues as the one you're experiencing. You can then check it step-by-step by hand relatively easy. — Martijn
– Martijn, Commented May 7, 2018 at 9:35
Btw, why are you updating the costs of the neighbours of already-processed nodes at the beginning of your loop? Aren't you doing this already when you process one of the nodes? It seems like an unnecessary amount of extra time spent on a task with no benefits. — Martijn
– Martijn, Commented May 7, 2018 at 9:39

julhien · Accepted Answer · 2018-05-07 09:44:51Z

2

Some parts of the algorithm seem wrong : Actually the source shouldn't be already in processed at the beginning. It should just be the only vertex with distance 0. It will then be selected as the first smallest_key. Therefore the beginning of the while loop where you compute all scores will not be needed anymore. The only part that will need to perform updates is the update of the distances of the neighbors of the smallest_key at the end of the loop.

def dijkstra(graph, s):
    processed = set([])
    vertexes = set([])
    distances = {}
    ans = []
    heap = priority_dict()
    for i in graph:
        vertexes.add(i)
        distances[i] = 0
        if i != s:
            heap[i] = float('inf')
        else:
            heap[i] = 0 
    while processed != vertexes:
        smallest_value = heap[heap.smallest()]
        smallest_key = heap.pop_smallest()
        processed.add(smallest_key)
        distances[smallest_key] = smallest_value
        for j in graph[smallest_key]:
            if j in heap:
                old_val = heap[j]
                new_val = min(old_val, distances[smallest_key] + graph[smallest_key][j])
                heap[j] = new_val
    list_ = [7,37,59,82,99,115,133,165,188,197]
    for i in list_:
        ans.append(distances[i])
    return ans

answered May 7, 2018 at 9:44

julhien

914 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Martijn Over a year ago

You might even replace distances[smallest_key] by smallest_value as it was just assigned to this value.

georgeB Over a year ago

I updated the code following your advice but the output is the same as before but still wrong..

julhien Over a year ago

Maybe the problem is somewhere else. Are you sure of your input graph and of your heap implementation ?

georgeB Over a year ago

I am sure about my graph implementation because i also used another one i found online which was part of a dijkstra implementation with correct results and the graph was the same. The heap implementation was not implemented by me, obviously. The heap implementation does what has to do. I tested it.

georgeB Over a year ago

I tried with a different heap, heapdict (pypi.org/project/HeapDict/#description) and still my algo outputs wrong answers...

Collectives™ on Stack Overflow

dijkstra implementation in python - output is not always correct

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related