如何在图中找到两条顶点不相交的路径，两条路径具有相同的源但不同的目的地？
How to find 2 vertex-disjoint paths in a graph with both paths having same source but different destination?
让我们考虑一下这张图：
假设
我想要第一条路径，源为 A，目标为 H 和
我想要第二条路径，源为 A，目标为 D。
我无法应用 suurballe 算法，因为它仅适用于具有相同源和相同目标的路径。
预期 O/p 是第一条路径 => A-E-F-G-H，第二条路径 => A-B-C-D。这两个是顶点不相交的路径。
在这种情况下如何计算2个顶点不相交的路径？
一种对很多问题都非常有效的方法是思考如何将其转化为您可以解决的问题。
在这种情况下：您已经知道Suurballe算法可以解决顶点不相交路径的问题，如果两者的目标顶点相同。
因此，要解决您的问题，您只需在图形中添加一个顶点 X 并连接 D 和 H 给它。然后用开始 A 和目标 X 执行 Suurballe 算法，并从返回路径的末尾删除 X .由于到达 X 的唯一途径是通过 D 和 H，它们必须是X.
之前的路径
让我们考虑一下这张图：
假设 我想要第一条路径，源为 A，目标为 H 和 我想要第二条路径，源为 A，目标为 D。
我无法应用 suurballe 算法，因为它仅适用于具有相同源和相同目标的路径。 预期 O/p 是第一条路径 => A-E-F-G-H，第二条路径 => A-B-C-D。这两个是顶点不相交的路径。 在这种情况下如何计算2个顶点不相交的路径？
一种对很多问题都非常有效的方法是思考如何将其转化为您可以解决的问题。
在这种情况下：您已经知道Suurballe算法可以解决顶点不相交路径的问题，如果两者的目标顶点相同。 因此，要解决您的问题，您只需在图形中添加一个顶点 X 并连接 D 和 H 给它。然后用开始 A 和目标 X 执行 Suurballe 算法，并从返回路径的末尾删除 X .由于到达 X 的唯一途径是通过 D 和 H，它们必须是X.
之前的路径