5

可能重复：
[python]：两个节点之间的路径

谁能指出一些有关如何执行此操作的资源？我正在networkx用作我的python库。

谢谢！

4

3 回答 3

6

这是基于 Alex Martelli 的回答，但应该可以。这取决于source_node.children产生一个迭代的表达式，该迭代将迭代source_node. 它还依赖于==操作员有一种工作方式来比较两个节点以查看它们是否相同。使用is可能是更好的选择。显然，在您使用的库中，获取所有子项的可迭代的语法是graph[source_node]，因此您需要相应地调整代码。

def allpaths(source_node, sink_node):
    if source_node == sink_node: # Handle trivial case
        return frozenset([(source_node,)])
    else:
        result = set()
        for new_source in source_node.children:
            paths = allpaths(new_source, sink_node, memo_dict)
            for path in paths:
                path = (source_node,) + path
                result.add(path)
        result = frozenset(result)
        return result

我主要担心的是，这会进行深度优先搜索，当从源到一个节点的多个路径时，它会浪费精力，这些路径都是源的孙子、曾孙等，但不一定是接收器的父节点。如果它记住了给定源和汇节点的答案，则可以避免额外的工作。

这是一个如何工作的示例：

def allpaths(source_node, sink_node, memo_dict = None):
    if memo_dict is None:
        # putting {}, or any other mutable object
        # as the default argument is wrong 
        memo_dict = dict()

    if source_node == sink_node: # Don't memoize trivial case
        return frozenset([(source_node,)])
    else:
        pair = (source_node, sink_node)
        if pair in memo_dict: # Is answer memoized already?
            return memo_dict[pair]
        else:
            result = set()
            for new_source in source_node.children:
                paths = allpaths(new_source, sink_node, memo_dict)
                for path in paths:
                    path = (source_node,) + path
                    result.add(path)
            result = frozenset(result)
            # Memoize answer
            memo_dict[(source_node, sink_node)] = result
            return result

这还允许您在调用之间保存记忆字典，因此如果您需要计算多个源和接收节点的答案，您可以避免大量额外的工作。

于 2010-07-19T05:06:52.607 回答
2

这个实际上适用于networkx，它是非递归的，这对于大型图可能很好。

def find_all_paths(graph, start, end):
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        print 'PATH', path

        path = path + [start]
        if start == end:
            paths.append(path)
        for node in set(graph[start]).difference(path):
            queue.append((node, end, path))
    return paths
于 2011-04-16T00:07:09.590 回答
1

我不确定是否有可用的特殊优化——在寻找其中任何一个之前，我会做一个简单的递归解决方案，比如（仅使用 networkx 的功能，即按节点索引图形会产生可迭代的结果邻居节点[[一个字典，在networkx的情况下，但我没有特别使用它]]）......：

def allpaths(G, source_nodes, set_of_sink_nodes, path_prefix=()):
  set_of_result_paths = set()
  for n in source_nodes:
    next_from_n = []
    for an in G[n]:
      if an in set_of_sink_nodes:
        set_of_result_paths.add(path_prefix + (n, an))
      else:
        next_from_n.append(an)
    if next_from_n:
      set_of_result_paths.update(
          allpaths(G, next_from_n, set_of_sink_nodes, path_prefix + (n,)))
  return set_of_result_paths

这应该是可以证明是正确的（但我不会做证明，因为它已经很晚了，我很累而且头脑模糊;-) 并且可用于验证任何进一步的优化;-)。

我尝试的第一个优化是某种简单的记忆：如果我已经计算了从某个节点 N 到任何目标节点的路径集（无论我进行计算时导致 N 的前缀是什么），我都可以存储如果以及当我通过不同的路线再次到达 N 时，请避免在键 N 下的字典中进行进一步的重新计算；-)。

于 2010-07-19T06:17:50.593 回答