CODEWITHSUNDEEP
pythonalgorithmshortest-pathdijkstra
noobita
noobita

Reputation: 65

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

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()

Upvotes: 0

Views: 154

Answers (1)

M Oehm
M Oehm

Reputation: 29126

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

Upvotes: 1

Related Questions