# собираем граф из массива
def build_graph(arr, fin):
    graph = {}
    for node in arr:
        if not graph.get(node[0]):
            graph[node[0]] = {}
        graph[node[0]][node[1]] = node[2]
    graph[fin] = {}
    return graph

# первоначальное состояние переменных
# costs - общая стоимость перехода в эту ноду
# parents - сопоставление нод и родителей
def fill_initial_state(graph, start, fin):
    costs = {}
    parents = {}
    for node in graph[start].keys():
        costs[node] = graph[start][node]
        parents[node] = start
    costs[fin] = 0
    parents[fin] = None
    return (costs, parents)

# поиск максимальнойной стоимости для следующего шага
def find_highest_cost(costs, processed):
    highest_cost = 0
    highest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost > highest_cost and node not in processed:
            highest_cost = cost
            highest_cost_node = node
    return highest_cost_node

# массив нод проделанного пути
def get_path(parents, start, fin):
    paths = [fin]
    value = parents[fin]

    while value != start:
        paths.append(value)
        value = parents[value]
    paths.append(start)
    return paths[::-1]

# Используем алгоритм Дейскры для поиска пути с минимальной стоимостью
def solve(graph, start, fin):
    graph = build_graph(data, fin)
    processed = []
    (costs, parents) = fill_initial_state(graph, start, fin)
    node = find_highest_cost(costs, processed)
    while node is not None:
        cost = costs[node]
        neighbors = graph[node]
        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if costs[n] < new_cost:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        node = find_highest_cost(costs, processed)
    path = get_path(parents, start, fin)

    return (costs[fin] / (len(path) - 1), path)
data = [
    [1, 2, 98],
    [1, 3, 50],
    [1, 4, 20],
    [2, 4, 99],
    [3, 4, 70]
]

(probability, path) = solve(data, 1, 4)
print("probability: ", probability, " path: ", path)