find_paths[s, t, d, k]

这个问题早已有答案。然而，没有人展示一种更灵活的算法来完成同样的事情。因此，我也想提出我的想法。

我个人认为形式为find_paths[s, t, d, k]的算法很有用，其中：

• s是起始节点
• t是目标节点
• d是搜索的最大深度
• k是要查找的路径数

使用编程语言的无穷大形式来代替d和k将会给您所有的路径§。

§ 显然，如果你使用了有向图并且想要在s和t之间找到所有的无向路径，那么你必须两个方向都运行这个算法：

find_paths[s, t, d, k] <join> find_paths[t, s, d, k]

---

辅助函数

我个人喜欢递归，尽管有时可能很困难，但首先让我们定义我们的辅助函数：

def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
  current_path.append(current)

  if current_depth > max_depth:
    return

  if current == goal:
    if len(paths_found) <= number_of_paths_to_find:
      paths_found.append(copy(current_path))

    current_path.pop()
    return

  else:
    for successor in graph[current]:
    self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)

  current_path.pop()

主要功能

话虽如此，核心功能却很简单：

def find_paths[s, t, d, k]:
  paths_found = [] # PASSING THIS BY REFERENCE  
  find_paths_recursion(s, t, 0, d, k, [], paths_found)

---

首先，让我们注意几点：

• 上述伪代码是多种语言的结合 - 但最接近Python（因为我刚刚在编码）。严格的复制粘贴将不起作用。
• []是未初始化的列表，请将其替换为您选择的编程语言的等效物。
• paths_found通过引用传递。很明显，递归函数不返回任何内容。请适当处理此问题。
• 这里的graph假定某种形式的hashed结构。有大量实现图的方法。无论哪种方式，graph[vertex]都可以让您获得有向图中相邻顶点的列表 - 请相应调整。
• 这假定您已经预处理以删除“扣环”（自环），循环和多边形。

gg1=nx.from_edgelist([('A','B'),('A','C'),('B','A'),('B','D'),('B','E'),('B','F'),('C','A'),('C','E'),
                  ('C','F'),('D','B'),('E','C'),('E','F'),('F','B'),('F','C'),('F','E')],create_using=nx.DiGraph)

pd.Series(nx.all_simple_paths(gg1, source='B', target='E'))

输出

0       [B, A, C, E]
1    [B, A, C, F, E]
2             [B, E]
3       [B, F, C, E]
4          [B, F, E]
dtype: object

我找到了一种方法来枚举包括具有循环的无限路径在内的所有路径。

http://blog.vjeux.com/2009/project/project-shortest-path.html

查找原子路径和循环

Definition

我们想要做的是找到从点A到点B的所有可能路径。由于涉及到循环，你不能只是一遍又一遍地枚举它们。相反，你需要找到不会循环的原子路径和最小可能的循环（你不希望你的循环重复出现）。
我最初提出的原子路径定义是一条不经过同一节点两次的路径。然而，我发现这并不包含所有的可能性。经过一些思考，我明白了，节点并不重要，而边才是！因此，一个原子路径是一条不经过同一边两次的路径。
这个定义很方便，也适用于循环：点A的一个原子循环是一条从点A开始，以点A结束的原子路径。 实现

Atomic Paths A -> B

为了获取从A点开始的所有路径，我们将从A点递归地遍历图。在经过一个子节点时，我们会创建一个子节点->父节点的链接，以便知道我们已经经过的所有边缘。在我们进入该子节点之前，我们必须遍历该链接列表，并确保指定的边缘尚未被穿过。
当我们到达目标点时，我们可以存储找到的路径。

Freeing the list

当你想要释放链接列表时，会出现一个问题。它基本上是以相反顺序链接的树。解决方案是将该列表双重链接，并在找到所有原子路径后，从起始点释放树。

但是一个聪明的解决方案是使用引用计数（受垃圾回收启发）。每次向父级添加链接时，都会将其引用计数加1。然后，当您到达路径的末尾时，向后移动并在引用计数等于1时释放。如果它更高，则只需删除一个并停止。

Atomic Cycle A

寻找A的原子循环与寻找从A到A的原子路径相同。但是我们可以进行几个优化。首先，当我们到达目标点时，只有当边缘成本之和为负时，我们才想保存路径：我们只想通过吸收循环。

正如您之前所看到的，寻找原子路径时会遍历整个图形。相反，我们可以将搜索区域限制在包含A的强连通分量中。查找这些组件需要使用Tarjan算法对图进行简单遍历。

结合原子路径和循环

此时，我们拥有从A到B的所有原子路径以及每个节点的所有原子循环，现在我们要组织一切以获得最短路径。从现在开始，我们将研究如何在原子路径中找到最佳的原子循环组合。

补充Casey Watson的答案，这里提供另一个Java实现。 将访问过的节点初始化为起始节点。

private void getPaths(Graph graph, LinkedList<String> visitedNodes) {
                LinkedList<String> adjacent = graph.getAdjacent(visitedNodes.getLast());
                for(String node : adjacent){
                    if(visitedNodes.contains(node)){
                        continue;
                    }
                    if(node.equals(END)){
                        visitedNodes.add(node);
                        printPath(visitedNodes);
                        visitedNodes.removeLast();
                    }
                    visitedNodes.add(node);
                    getPaths(graph, visitedNodes);
                    visitedNodes.removeLast();  
                }
            }

这是我脑海中的一个想法：

1. 找到一个连接。（深度优先搜索可能是一个不错的算法，因为路径长度并不重要。）
2. 禁用最后一段。
3. 尝试从之前禁用的连接前面的最后一个节点找到另一个连接。
4. 重复步骤2-3，直到没有更多的连接。

据我所知，Ryan Fox（58343），Christian（58444）和您自己（58461）提供的解决方案是最好的。我认为广度优先遍历在这种情况下并没有帮助，因为您将无法获取所有路径。例如，对于边缘（A，B），（A，C），（B，C），（B，D）和（C，D），您将获得路径ABD和ACD，但不会获得ABCD。

正如其他帖子中所描述的那样，问题的核心在于使用深度优先搜索算法递归地搜索图形以查找通信终节点之间所有路径的组合。

算法本身从您提供的起始节点开始，检查其所有出站链接，并通过扩展出现的搜索树的第一个子节点进行进展，逐渐深入搜索，直到找到目标节点或遇到没有子节点的节点为止。

然后搜索会回溯，返回到最近尚未完成探索的节点。

我最近博客了这个非常主题，同时发布了一个示例C++实现。