networkx中最可能的路径

Question

我有一个邻接矩阵（作为一个数据帧），每个单元都有从a到B的概率

行是“从”，列是“到”。每行的总和是1.0。

我已经建立了一个网络图，现在概率是图的“权重”。

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

编辑：输入是图G、节点“源”和节点“目标”，为简单起见，它们确实通过多条路径连接。我想在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开始的最短路径。按照dijkstra算法，最短路径将给出：

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