Can someone detect error in this code to implement dijkstra's algorithm using python?

Question

I am trying to implement dijkstra's algorithm (on an undirected graph) to find the shortest path and my code is this.

Note: I am not using heap/priority queue or anything but an adjacency list, a dictionary to store weights and a bool list to avoid cycling in the loops/recursion forever. Also, the algorithm works for most test cases but fails for this particular one here: https://ideone.com/iBAT0q

Important : Graph can have multiple edges from v1 to v2 (or vice versa), you have to use the minimum weight.

import sys

sys.setrecursionlimit(10000)

def findMin(n):
    for i in x[n]:
        cost[n] = min(cost[n],cost[i]+w[(n,i)])
def dik(s):
    for i in x[s]:
        if done[i]:
            findMin(i)
            done[i] = False
            dik(i)
    return
q = int(input())
for _ in range(q):
    n,e = map(int,input().split())
    x = [[] for _ in range(n)]
    done =  [True]*n
    w = {}
    cost = [1000000000000000000]*n
    for k in range(e):
        i,j,c = map(int,input().split())
        x[i-1].append(j-1)
        x[j-1].append(i-1)
        try:                                       #Avoiding multiple edges
            w[(i-1,j-1)] = min(c,w[(i-1,j-1)])
            w[(j-1,i-1)] = w[(i-1,j-1)]
        except:
            try:
                w[(i-1,j-1)] = min(c,w[(j-1,i-1)])
                w[(j-1,i-1)] = w[(i-1,j-1)]
            except:
                w[(j-1,i-1)] = c
                w[(i-1,j-1)] = c
    src = int(input())-1
    #for i in sorted(w.keys()):
    #   print(i,w[i])
    done[src] = False
    cost[src] = 0
    dik(src)          #First iteration assigns possible minimum to all nodes
    done = [True]*n     
    dik(src)          #Second iteration to ensure they are minimum
    for val in cost:
        if val == 1000000000000000000:
            print(-1,end=' ')
            continue
        if val!=0:
            print(val,end=' ')
    print()

M Oehm · Accepted Answer · 2017-08-31 19:40:04Z

1

The optimum isn't always found in the second pass. If you add a third pass to your example, you get closer to the expected result and after the fourth iteration, you're there.

You could iterate until no more changes are made to the cost array:

done[src] = False
cost[src] = 0
dik(src)

while True:
    ocost = list(cost)          # copy for comparison
    done = [True]*n     
    dik(src)
    if cost == ocost:
        break

answered Aug 31, 2017 at 19:40

M Oehm

29.2k3 gold badges36 silver badges44 bronze badges

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

2 Comments

noobita Over a year ago

Thanks for going through the messed up code. However, it has been brought to my notice that the algorithm itself is not dijkstras but some messed and incomplete version of bellman ford. I changed my approach and solved it the other way. Thanks! :)

M Oehm Over a year ago

Yes, it isn't Dijkstra's algorithm, but that name is often given to any old algorithm that performs shortest-path search. Glad you have found a solution.

Collectives™ on Stack Overflow

Can someone detect error in this code to implement dijkstra's algorithm using python?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related