Why it resulting a "list index out of range error" on this dijkstra algorithm

103 Views Asked by At

I tried to implement a dijkstra algorithm on my own graph but it doesn't run instead it says that "list index out of range"

here is the code that i tried

it works on a smaller graph like with 6 nodes but mine has 39 nodes and the maker of this code said that "At every iteration analyze the list and how the list is accessed using print()..it will help troubleshoot the error" what is that supposed to mean ?

so after a while i realized it resulting that because the algorithm reached a dead end like in node (A,B,C,AL) so when i tried to go from A to F it reached a dead end on B, can i get a help how to fix this please ?

import sys
from heapq import heapify, heappush, heappop

def dijsktra(graph,src,dest):
    inf = sys.maxsize
    node_data = {'A':{'cost':inf,'pred':[]},
    'B':{'cost':inf,'pred':[]},
    'C':{'cost':inf,'pred':[]},
    'D':{'cost':inf,'pred':[]},
    'E':{'cost':inf,'pred':[]},
    'F':{'cost':inf,'pred':[]},
    'G':{'cost':inf,'pred':[]},
    'H':{'cost':inf,'pred':[]},
    'I':{'cost':inf,'pred':[]},
    'J':{'cost':inf,'pred':[]},
    'K':{'cost':inf,'pred':[]},
    'L':{'cost':inf,'pred':[]},
    'M':{'cost':inf,'pred':[]},
    'N':{'cost':inf,'pred':[]},
    'O':{'cost':inf,'pred':[]},
    'P':{'cost':inf,'pred':[]},
    'Q':{'cost':inf,'pred':[]},
    'R':{'cost':inf,'pred':[]},
    'S':{'cost':inf,'pred':[]},
    'T':{'cost':inf,'pred':[]},
    'U':{'cost':inf,'pred':[]},
    'V':{'cost':inf,'pred':[]},
    'W':{'cost':inf,'pred':[]},
    'X':{'cost':inf,'pred':[]},
    'Y':{'cost':inf,'pred':[]},
    'Z':{'cost':inf,'pred':[]},
    'AA':{'cost':inf,'pred':[]},
    'AB':{'cost':inf,'pred':[]},
    'AC':{'cost':inf,'pred':[]},
    'AD':{'cost':inf,'pred':[]},
    'AE':{'cost':inf,'pred':[]},
    'AF':{'cost':inf,'pred':[]},
    'AG':{'cost':inf,'pred':[]},
    'AH':{'cost':inf,'pred':[]},
    'AI':{'cost':inf,'pred':[]},
    'AJ':{'cost':inf,'pred':[]},
    'AK':{'cost':inf,'pred':[]},
    'AL':{'cost':inf,'pred':[]},
    'AM':{'cost':inf,'pred':[]},
    }
    node_data[src]['cost'] = 0
    visited = []
    temp = src
    for i in range(38):
        if temp not in visited: # TODO: Reassign source
            visited.append(temp)
            min_heap = []
            for j in graph[temp]:
                if j not in visited:
                    cost = node_data[temp]['cost'] + graph[temp][j]
                    if cost < node_data[j]['cost']:
                        node_data[j]['cost'] = cost
                        node_data[j]['pred'] = node_data[temp]['pred'] + [temp]
                    heappush(min_heap,(node_data[j]['cost'],j))
        heapify(min_heap)
        temp = min_heap[0][1] 
    print("Shortest Distance: " + str(node_data[dest]['cost']))
    print("Shortest Path: " + str(node_data[dest]['pred'] + list(dest)))


if __name__ == "__main__":
    graph = {
        'A':{'D':105.3},
            'B':{'E':65},
            'C':{'AM':103.4},
            'D':{'A':105.3,'E':132.8,'J':165.8},
            'E':{'B':65,'D':132.8,'F':176.6,'H':78.3},
            'F':{'E':176.6,'R':181.8,'AM':20.3},
            'G':{'H':63,'K':57.2},
            'H':{'E':78.3,'G':63,'I':65,'O':101.2},
            'I':{'H':65,'P':104},
            'J':{'D':165.8,'K':125.6,'L':25.9},
            'K':{'G':57.2,'J':125.6,'N':37.5},
            'L':{'J':25.9,'M':68,'Y':177.7},
            'M':{'L':25.9,'N':56,'V':124},
            'N':{'K':37.5,'M':56,'O':77.4},
            'O':{'H':101.2,'N':77.4,'P':70.2,'W':128.6},
            'P':{'I':104,'O':70.2,'Q':68},
            'Q':{'P':68,'R':45,'T':102.9},
            'R':{'F':181.8,'Q':45,'S':51},
            'S':{'R':51,'U':104.3,'AM':193.3},
            'T':{'Q':102.9,'U':84.35,'X':21.6},
            'U':{'S':104.3,'A':84.35,'AF':160.7},
            'V':{'M':124,'W':128,'Z':45},
            'W':{'O':128.6,'V':128,'X':150.7,'AD':132.9},
            'X':{'T':21.6,'W':150.7,'AE':166.8},
            'Y':{'L':177.7,'Z':100.9,'AA':39.8},
            'Z':{'V':45,'Y':100.9,'AB':34},
            'AA':{'Y':39.8,'AB':100.3,'AH':258.5},
            'AB':{'Z':34,'AA':100.3,'AC':47.8},
            'AC':{'AB':47.8,'AD':126,'AH':60.37},
            'AD':{'W':132.9,'AE':110.2,'AK':93.14,'AC':126},
            'AE':{'X':166.8,'AI':82.2,'AD':110.2},
            'AF':{'U':160.7,'AG':13.7,'AI':181.2},
            'AG':{'AF':13.7},
            'AH':{'AA':285.5,'AC':60.37,'AJ':33.8},
            'AI':{'AE':82.2,'AF':181.2,'AK':110},
            'AJ':{'AH':33.8,'AK':119.3,'AL':52},
            'AK':{'AD':93.14,'AI':110,'AJ':119.3},
            'AI':{'AJ':52},
            'AM':{'C':103.4,'S':193.3,'F':20.3}
    }

    source = 'A'
    destination = 'F'
    dijsktra(graph,source,destination)

it said error instead on this line

temp = min_heap[0][1]
0

There are 0 best solutions below