查找节点之间所有简单路径的问题？

通过在未加权图上使用dijkstra算法找到两个节点之间的所有简单路径是否可行？如果是，如何？查找节点之间所有简单路径的问题？

2012-07-03 Rose BEck

“*如果是，那么怎么办？*”不，要回答合理，我们需要你的努力。 [你有什么尝试]（http://mattgemmell.com/2008/12/08/what-have-you-tried/）。 – Lion

Dijkstra的算法旨在用于查找*最短路径。您不需要它来查找两个节点之间的* all *路径。这是功课吗？ – reuben

在图中确保路径的数量是有限的吗？（例如DAG确保）或者您对所有*简单*路径感兴趣，而不是所有路径？ – amit

所有的Dijkstra首先表现就像上图未加权广度握拳的搜索，这样它没有任何意义，用于这项任务。

得到两个顶点之间的所有路径的典型方法是使用修改depth first search。

2012-07-03 06:22:12

@你谈到了修改的DFS ...但是链接只给出了关于DFS .... DFS必须被修改以获得两个顶点之间的所有路径。 –

我想你只需要找到在DFS中遇到顶点的次数？ – sukunrt

@RoseBEck是的，我发送的链接只是关于DFS。你的问题是“是否可以找到...”，所以我的答案就足够了 - 不是不可行。至于我提到的DFS算法 - 你需要修改你标记为已访问的节点的方式（因为我不确定这是否是作业我不愿意给出更详细的答案） –

通过使用标准Floyd-Warshall算法的修改，您应该能够计算图中任意两个节点之间的简单路径。你可能想看看UVA Online Judge的this 问题。它的解决方案可以在互联网上免费获得。

2012-07-05 07:52:46

回答