所有可能路径算法

Question

我对数学算法不是很熟悉，并且需要将其用于我正在从事的项目。我找到了从 A 点到 B 点的答案，但 none 确实符合我要找的内容。我正在寻找最省时的算法来完成这项任务：

对于输入：

Points {
    In
    Out
}

[Bridge]Points = {
    "AB-1" = {"A", "B"}
    "AB-2" = {"A", "B"}
    "BA-1" = {"B", "A"}
    "BA-2" = {"B", "A"}
    "AC-1" = {"A", "C"}
    "AC-2" = {"A", "C"}
    "CA-1" = {"C", "A"}
    "CA-2" = {"C", "A"}
    "BC-1" = {"B", "C"}
    "BC-2" = {"B", "C"}
    "CB-1" = {"C", "B"}
    "CB-2" = {"C", "B"}
}

每个“桥”代表 2 个“点”：第一个值是“输入”，第二个值是“输出”。

每条路径只能使用每个唯一的网桥一次。不同的桥可以有相同的in/out（比如"BC-1","BC-2", ..），和每个独特的桥必须有不同的进出（"AA-1" = {"A", "A"} 是不可能的）。

目标是在给定起点和终点的情况下获得所有可能的路径，起点和终点可以是相同的点 (A->A, B ->B, ..).

对于 A 到 A 的预期输出：

AB-1 -> BA-1
AB-1 -> BA-2
AB-2 -> BA-1
AC-1 -> CA-2
AB-1 -> BA-1 -> AB-2 -> BA-2
AB-1 -> BA-2 -> AC-1 -> CB-2 -> BA-1
AC-2 -> CA-1 -> AB-1 -> BA-2
AC-1 -> CA-1 -> AB-2 -> BC-1 -> CA-2
...

此外，定义最大路径长度（以避免在算法中进行后续处理）的可能性是可选的，但非常有趣。感谢您的宝贵时间，非常感谢您的建议。

Answer 1

可以使用这样的递归（伪代码）：

findPath(from, to, path_to_from) {
  if from == to { output path_to_from }
  for all bridges going out from 'from' that were not already used in path_to_from {
    findPath(bridge.out, to, path_to_from + bridge)
  }
}

并用findPath(A, B, empty_path)调用它输出从A到B的所有路径。

所有可能路径算法

All possible paths algorithm

algorithm

mathematical-optimization

graph-algorithm