Dijkstra algorithm finds lowest cost but can't find the path

49 Views Asked by At

Here is my dijkstra implementation which finds the lowest cost from top-left to bottom-right.

input.txt:

2413
3215
3255
3446

(2,3,2,2,4,4,6)

Code:

import sys

with open('input.txt', 'r') as file:
    hashmap = file.read().split('\n')
hashmap = [list(map(int, list(item))) for item in hashmap]

nodes = {}
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

for i in range(0, len(hashmap)):
    for j in range(0, len(hashmap[0])):
        nodes[(i, j)] = sys.maxsize
nodes[(0, 0)] = hashmap[0][0]

current_val = 0

while len(nodes) > 0:
    current_ind = min(nodes, key=nodes.get)
    current_val = nodes[current_ind]
    print(nodes)
    for i in dirs:
        a, b = current_ind[0]+i[0], current_ind[1]+i[1]
        if (a, b) in nodes:
            nodes[(a, b)] = min(hashmap[a][b] + current_val, nodes[(a, b)])
    if current_ind == (len(hashmap)-1, len(hashmap[0])-1):
        answer = nodes[current_ind]
    del nodes[current_ind]

print(answer)

I can't figure out how to find the way that provides the lowest cost.

0

There are 0 best solutions below