наиболее вероятный путь в сети x

Question

У меня была матрица смежности (как pandas фрейм данных), в каждой ячейке есть вероятность перехода от А к В

Строка - это «от», а столбец - «к». Сумма каждой строки равна 1,0.

Я построил график networkx, и теперь вероятности являются «весами» графика.

Я пытаюсь найти наиболее вероятный путь - то есть произведение весов наименьшее, а не сумма. Я знаю, что кратчайший путь сети x находит оптимальный путь в терминах суммы весов. Как мне найти оптимальный путь с точки зрения оптимального продукта?

Редактировать: Входными данными являются граф G, узел «ИСТОЧНИК» и узел «ЦЕЛЬ», которые для простоты действительно связаны несколькими путями. Я хочу найти наиболее вероятный путь между ними в G

Thx

Answer 1

Одним из способов сделать это может быть поиск всех путей от заданного источника к цели, используя nx.all_simple_paths, и, перебирая все промежуточные ребра, умножьте их соответствующие веса ребер, чтобы отслеживать тот, который дает наименьший полученный вес.

Следуя этой логике c, мы можем сделать что-то вроде:

def shortest_path_w_prod(G, source, target):
    paths = list(nx.all_simple_paths(G, source, target))
    w_path = []
    for path in paths:
        w = 1
        for edge in zip(path[:-1],  path[1:]):
            w *= G.get_edge_data(*edge)['weight']
        w_path.append(w)
    min_path_ix = w_path.index(min(w_path))
    return paths[min_path_ix]

---

Давайте посмотрим на примере:

l = [('a', 'f', 2), ('f', 'c', .1), ('r', 'e', 3), ('d', 'e', .4), ('e', 'a', 5), ('a', 'b', 2), ('c', 'a', 1.5), ('d', 'a', 2.), ('c', 'e', 0.2)]
G = nx.Graph()
G.add_weighted_edges_from(l)

Что выглядит так:

pos = nx.spring_layout(G, scale=20, k=3/np.sqrt(G.order()))
nx.draw(G, pos=pos,
        node_color='lightblue', 
        with_labels=True, 
        node_size=500)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)

Мы получим, что кратчайший путь, следуя описанным логикам c, будет:

shortest_path_w_prod(G, 'b', 'r')
# ['b', 'a', 'f', 'c', 'e', 'r']

В то время как кратчайший путь из nx.shortest_path, следуя алгоритму Дейкстры, даст:

nx.shortest_path(G, 'b', 'r', 'weight')
# ['b', 'a', 'c', 'e', 'r']