Алгоритм Дейкстры с нахождением наиболее вероятного пути

    def Dijkstra(N, S, matrix, end):
        valid = [True] * N
        weight = [0.01] * N
        weight[S] = 1.0
        ves=[0.0]*N
        result=[]
        for i in range(N):
            min_weight = 0.0
            ID_min_weight = 0.0
            for i in range(len(weight)):
                if valid[i] and weight[i] > min_weight:
                    min_weight = weight[i]
                    ID_min_weight = i
            for i in range(N):
                if (round(weight[ID_min_weight] * matrix[ID_min_weight][i],4) > weight[i] and i<end+1):
                    weight[i] = round(weight[ID_min_weight] * matrix[ID_min_weight][i],4)
                    ves[i]=matrix[ID_min_weight][i]
            valid[ID_min_weight] = False
    
        result.append(end + 1)
        i = end
        test = end
        while (i!=0):
            for j in range(end, -1, -1):
                if (ves[i]!=0.0 and round(weight[i] / ves[i],4) == weight[j] and i<=test):
                    result.append(j+1)
                    test=j
            i -= 1
    
    
        result.reverse()
        print (*result)
    
        return round(weight[end],4)
    
    str=[]
    matrix2=[]
    for i in input().split():
        str.append(int(i))
    
    N = str[0]   # Количество вершин
    M = str[1]   # Количество дуг
    begin = str[2]  # Начальная вершина
    end = str[3]    # Конечная вершина
    
    matrix = [[float (j) for j in input().split()] for i in range(M)]
    
    for i in matrix:
        if len(i)>3:
            exit()
    
    for i in range(N):
        matrix2.append([])
        for j in range(N):
            matrix2[i].append(0.01)
    
    for i in range(M):
        matrix2[int(matrix[i][0]-1)][int(matrix[i][1]-1)] = matrix[i][2]
    
    print(Dijkstra(N, begin-1, matrix2,end-1))