最近在做一个课题，我需要找到多重图中两个节点之间的所有简单路径。每条路径权重和不一样。

假如我建立一个简单的多重图代码如下：

>>> H=nx.MultiDiGraph()                   '''建立多重图'''
>>> H.add_edges_from([(0, 1), (0, 1),(1,2),(1,2)])          '''添加边'''
[0, 1, 0, 1]
>>> H[0][1][0]['weight']=0.1      '''为每条边添加权值'''
>>> H[0][1][1]['weight']=0.2
>>> H[1][2][0]['weight']=0.3
>>> H[1][2][1]['weight']=0.4

然后我用networkx中的all_simple_path()函数求0到2的简单路径如下：

 >>> for n in nx.all_simple_paths(H,0,2):
                            print n


[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
[0, 1, 2]
>>>

我现在有个问题，0到2之间有4条路径，我怎么才能知道上面四个结果分别对应的是哪一条路径？我应该如何修改all_simple_paths()函数

all_simple_path()函数的python代码如下：

 def all_simple_paths(G, source, target, cutoff=None):
    if source not in G:
        raise nx.NodeNotFound('source node %s not in graph' % source)
    if target not in G:
        raise nx.NodeNotFound('target node %s not in graph' % target)
    if cutoff is None:
        cutoff = len(G) - 1
    if G.is_multigraph():
        return _all_simple_paths_multigraph(G, source, target, cutoff=cutoff)
    else:
        return _all_simple_paths_graph(G, source, target, cutoff=cutoff)

def _all_simple_paths_multigraph(G, source, target, cutoff=None):
    if cutoff < 1:
        return
    visited = [source]
    stack = [(v for u, v in G.edges(source))]
    while stack:
        children = stack[-1]
        child = next(children, None)
        if child is None:
            stack.pop()
            visited.pop()
        elif len(visited) < cutoff:
            if child == target:
                yield visited + [target]
            elif child not in visited:
                visited.append(child)
                stack.append((v for u, v in G.edges(child)))
        else:  # len(visited) == cutoff:
            count = ([child] + list(children)).count(target)
            for i in range(count):
                yield visited + [target]
            stack.pop()
            visited.pop()

试一下权值可以量化，比如说 3 4 5 6量化为3X1,4X1,5X1,6X1，然后相当于在两点之间花了一张图，用图论的方法解决这个问题就可以了。希望采纳~

Dijkstra算法
http://blog.csdn.net/qq_35644234/article/details/60870719

利用图论基本算法就ok啦