两个节点之间的所有路径在图中

Question

我需要编写一个无信息搜索（广度优先搜索）程序，该程序接受两个节点并返回它们之间的所有路径。

public void BFS(Nod start, Nod end) {
            Queue<Nod> queue = new Queue<Nod>();
            queue.Enqueue(start);
            while (queue.Count != 0)
            {
                Nod u = queue.Dequeue();
                if (u == end)  break;
                else
                {
                    u.data = "Visited";
                    foreach (Edge edge in u.getChildren())
                    {
                        if (edge.getEnd().data == "")
                        {
                            edge.getEnd().data = "Visited";
                            if (edge.getEnd() != end)
                            {
                                edge.getEnd().setParent(u);
                            }
                            else
                            {
                                edge.getEnd().setParent(u);
                                cost = 0; 
                                PrintPath(edge.getEnd(), true);
                                edge.getEnd().data = "";
                                //return;
                            }
                        }
                        queue.Enqueue(edge.getEnd());
                    }
                }
            }
        }

我的问题是我只得到了两条路径，而不是全部路径，我不知道该如何编辑我的代码以获取所有路径。我的问题的输入基于这张地图：

- sebastian.roibu

---

这个图是无向的吗（从图片上看应该是）？如果是的话，我认为你需要研究一些动态规划，因为很多路径会共享一些子路径。只是想知道，你为什么想要所有可能的路径？ - aweis

图是无向的。我需要按照BFS顺序遍历节点。我想使用无信息搜索找到具有最小成本的所有可能性。 - sebastian.roibu

你是在寻找“所有路径”还是“所有最短路径”？为什么在找到目标后要使用break;？可能还有其他解决方案等待发现...此外，它一定要是BFS吗？我认为像迭代加深深度优先搜索这样的算法会更容易实现，以找到所有最短路径...但这可能只是我的想法：\ - amit

等等，里斯本到伦敦有直达连接？但维也纳到布达佩斯没有？我就在那列火车上！我强烈抗议这个图表。 - Martijn

无论现实生活中是什么都不重要。:-D - sebastian.roibu

你告诉那个想从维也纳去布达佩斯的人，结果误坐了错的火车！ - Martijn

Answer 1

广度优先搜索是一种生成所有可能路径的奇怪方法，原因在于需要跟踪每个BFS中的单个路径是否已经遍历了节点，而不是简单确定是否已经遍历过节点。

以下是一个简单的例子：

1----2
 \    \
  3--- 4----5

我们希望找出从1到5的所有路径。我们将1放入队列，然后是2和3，接着是4，最后是5。我们忽略了通过4到达5的两条路径。

我建议尝试使用深度优先搜索来解决这个问题，虽然使用广度优先搜索也可以通过一些思考来解决。每个加入队列的事物都应该是一条路径，而不是单个节点，这样就可以查看该路径是否已经访问过每个节点。虽然这样会浪费一些内存。

- dfb

---

我必须使用BFS来完成它，无论我使用多少内存都没有关系。 - sebastian.roibu

Answer 2

在BFS算法中，当你找到一个解决方案时，不能停止。一种想法是将你访问过的所有城市的数据设置为null，除了第一个城市，然后让函数继续运行一段时间。我没有时间为你写出代码片段，但如果你不理解我的想法，我会至少写出伪代码。如果你没理解我的想法，请在评论区留言提出问题，我会尽力解释得更好。

- Gabrielle

Answer 3

一个路径是一个顶点序列，其中没有重复的顶点。根据这个定义，您可以编写一个递归算法，它将按以下方式工作：向函数传递四个参数，称为 F(u, v, intermediate_list, no_of_vertices)，其中 u 是当前源（在我们递归时会更改），v 是目标，intermediate_list 是一个顶点列表，最初为空，每次使用一个顶点时，我们将其添加到列表中，以避免在路径中多次使用一个顶点，no_of_vertices 是我们希望找到的路径的长度，下限为 2，上限为顶点数 V。本质上，该函数应返回一个源为 u，目标为 v，每条路径长度为 no_of_vertices 的路径列表。创建一个初始空列表，并调用 F(u, v, {}, 2), F(u, v, {}, 3), ..., F(u, v, {}, V)，每次将 F 的输出与我们打算存储所有路径的列表合并。尝试实现这个算法，如果仍然有困难，我可以为您编写伪代码。

编辑：使用 BFS 解决上述问题：广度优先搜索是一种可用于探索图的所有状态的算法。您可以使用 BFS 探索给定图的所有路径图，并选择您想要的路径。对于每个顶点 v，将以下状态添加到队列中：(v, {v}, {v})，其中每个状态定义为：(current_vertex, list_of_vertices_already_visited, current_path)。现在，在队列不为空的情况下，弹出队列的顶部元素，对于当前顶点的每个边缘 e，如果尾顶点 x 在 list_of_vertices_already_visited 中不存在，则将新状态 (x, list_of_vertices_already_visited + {x}, current_path -> x) 推入队列，并在弹出它时处理每条路径。这样，您就可以搜索有向或无向图的整个路径图。

- Rahul Gulati

Answer 4

听起来像是作业。但是是有趣的那种。

以下是伪代码，采用深度优先而不是广度优先（因此应该转换为队列类型算法，并可能包含错误，但总体思路应该清晰明了。

class Node{
  Vector[Link] connections;
  String name;
}

class Link{
  Node destination;
  int distance;
}

Vector[Vector[Node]] paths(Node source, Node end_dest, Vector[Vector[Node]] routes){
  for each route in routes{
    bool has_next = false;
    for each connection in source.connections{
      if !connection.destination in route {
        has_next = true;
        route.push(destination);
        if (!connection.destination == end_dest){
          paths(destination, end_dest, routes);
        }
      }
    }
    if !has_next {
      routes.remove(route) //watch out here, might mess up the iteration
    }
  }
  return routes;
}

编辑：这实际上是你要找的答案吗？还是你真的想找到最短路径？如果是后者，请使用Dijkstra算法：http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

- Martijn

---

请不要仅发布没有解释的代码 - 特别是如果您认为这是作业 - 那么原始帖子会从中学到什么呢？ - amit

这是伪代码，因此任何实现都需要理解正在发生的事情。更不用说它是深度优先的，因此对于广度优先，他将需要重新制定计划，以便理解正在发生的事情。 - Martijn

Dijkstra算法使用了有启发性的搜索。由于我的算法需要在盲目状态下运行，因此我必须生成所有路径。 - sebastian.roibu

如果存在负值，则可以在http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm上找到Bellman-Ford算法的描述。 - Martijn

只有正值，但我需要没有启发式，只是盲目地查看。 - sebastian.roibu