networkx 中最可能的路径

Question

我有一个邻接矩阵（作为 pandas 数据框），每个单元格都是从 A 到 B 的概率

行是 "from"，列是 "to"。每行的总和为 1.0。

我构建了一个 networkx 图，现在概率是图的 "weights"。

我试图找到最可能的路径 - 即权重的乘积是最低的，而不是总和。我知道 networkx 最短路径根据权重总和找到最优路径。我如何根据最佳产品找到最佳路径？

编辑：输入是图G，节点"SOURCE"和节点"TARGET"，为简单起见，它们确实由多条路径连接。我想在 G

中找到它们之间最可能的路径

感谢

Answer 1

一种方法是使用 nx.all_simple_paths 寻找来自给定源和目标的所有路径，并在遍历所有中间边时，乘以它们各自的边权重，以跟踪给出最小结果权重的那个。

按照这个逻辑，我们可以做类似的事情：

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)

我们会得到最短路径，按照所描述的逻辑，将是：

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

而从 nx.shortest_path 开始的最短路径遵循 dijkstra 算法，将给出：

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

networkx 中最可能的路径

most probable path in networkx

pandas

algorithm

networkx

shortest-path