Визначення найкоротшого шляху в графі

Алгоритм Флойда-Уоршела

n=int(input())

a=[]

for i in range(n):

    a=a+[[int(i) for i in input().split()]]

for k in range(n): #{ k - проміжна вершина } 

  for i in range(n): #{ з i-ої вершини } 

    for j in range( n): #{ в j-у вершину } 

      a[i][j] = min(a[i][j], a[i][k] + a[k][j])

for i in range(n):

    print(*a[i])

Ще одна функція алгоритму Дейкстри

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

Де N — кількість вершин;
S — номер стартової вершини (з нуля);
matrix — матриця суміжності вихідного графа, де неіснуючі ребра мають бескінечну вагу;
В даному випадку бескінечність рівна 1000000