find_path.py

# Uses python3

# собираем граф из массива
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] / 100
        if not graph.get(node[1]):
            graph[node[1]] = {}
        graph[node[1]][node[0]] = node[2] / 100
    graph[fin] = {}
    return graph

# первоначальное состояние переменных
# costs - общая стоимость перехода в эту ноду
def fill_initial_state(graph, start, fin):
    costs = {}
    parents = {}
    for node in graph[start].keys():
        costs[node] = graph[start][node]
        parents[node] = start
    costs[start] = 1
    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)
    print(graph)
    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]
        print(costs)
        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], path)
data = [
    [1, 2, 52],
    [1, 3, 71],
    [1, 4, 83],
    [2, 3, 71],
    [3, 4, 93],
    [3, 5, 82],
    [2, 5, 99]
]

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