Алгоритм Дейкстры python

input.txt

-1 -1 -1 15 -1 -1 -1 20
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 2
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1

main.py

# Число которое мы будем считать бесконечностью
inf = 1000000


def Dijkstra(N, S, matrix):
    valid = [True] * N
    weight = [inf] * N
    weight[S] = 0
    for i in range(N):
        min_weight = inf+1
        ID_min_weight = -1
        for j in range(N):
            if valid[j] and weight[j] < min_weight:
                min_weight = weight[j]
                ID_min_weight = j
        for j in range(N):
            if weight[ID_min_weight] + matrix[ID_min_weight][j] < weight[j]:
                weight[j] = weight[ID_min_weight] + matrix[ID_min_weight][j]
        valid[ID_min_weight] = False
    return weight


def Main():
    #начальная вершина
    start = 0;
    #файл с матрицей смежности
    f = open('input.txt')

    matrix = [list(inf if a<0 else a for a in map(int, row.split())) for row in f.readlines()]

    for i, item in enumerate(Dijkstra(len(matrix), start, matrix)):
        if item < inf: print("К вершине {} мы можем дойти за минимальное расстояние {} ".format(i+1, item))



Main()