algorithm - 寻找节点之间所有简单路径的问题？

Question

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

Answer 1

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

Answer 2

首先，dijkstra 的行为就像在未加权图上的广度拳搜索，因此将它用于此任务没有任何意义。

获取两个顶点之间的所有路径的典型方法是使用修改的深度优先搜索。