在图中找到强制访问某些边而其他边不是强制访问的图中的最短路径
find shortest path in a graph that compulsorily visits certain Edges while others are not compulsory to visit
我有一个无向图，有大约 1000 个节点和 2000 条边，一个开始节点和一个结束节点。我必须从起始节点遍历到结束节点，通过所有强制边（大约 10 个），而不必遍历所有顶点或节点。是否有一个简单的解决方案，比如对现有的图遍历算法进行一些小改动？我该怎么做？
感谢您的帮助。:)
这个问题与 Find the shortest path in a graph which visits certain nodes 不同，因为我的问题是关于强制边而不是顶点。
编辑：强制边可以按任何顺序遍历。
从相关问题开始，假设您有一个图 G = (V, E)，您必须按给定顺序遍历 10 个特定边 E' = 1, ..., e10 > ∈ E，以及一个起始和结束节点s，v∈ V.您需要按给定顺序使用 E' 找到从 s 到 v 的最短距离。
您可以复制 10 张图表来完成此操作。从单个副本开始（即同构 t G = (V, E)），除了 e1 从第一个副本移动到第二个副本。在第二个副本中（再次同构 t G = (V, E)），删除 e1 ，并让 e2 从第二个副本移动到第三个副本。等等。在结果图中，运行 任何算法从第一个副本中的 s 到第 10 个副本中的 e。
解释：凭直觉想象你的图G是画在二维sheet纸上的。影印它，这样你就有了 10 份，然后将它们堆叠成 10 份纸（不过想象一下，每两份之间有一点 space）。现在稍微更改图表，以便从第一个 sheet 上升到第二个 sheet 的唯一方法是通过边 e1 从底部 sheet 到第二个 sheet。从第二个 sheet 上升到第三个 sheet 的唯一方法是通过边 e2从第二个 sheet 到第三个 sheet，依此类推。你的问题是求最短路径，从最下面sheets对应的节点开始，到e[=43]对应的节点结束=] 在顶部 sheet.
要解决原始问题，只需对 E' 的所有可能排列重复此操作。请注意，有 10 个！ ~ 3.5e6 种可能性，并没有那么多。
我有一个无向图，有大约 1000 个节点和 2000 条边，一个开始节点和一个结束节点。我必须从起始节点遍历到结束节点，通过所有强制边（大约 10 个），而不必遍历所有顶点或节点。是否有一个简单的解决方案，比如对现有的图遍历算法进行一些小改动？我该怎么做？
感谢您的帮助。:)
这个问题与 Find the shortest path in a graph which visits certain nodes 不同，因为我的问题是关于强制边而不是顶点。
编辑：强制边可以按任何顺序遍历。
从相关问题开始，假设您有一个图 G = (V, E)，您必须按给定顺序遍历 10 个特定边 E' = 1, ..., e10 > ∈ E，以及一个起始和结束节点s，v∈ V.您需要按给定顺序使用 E' 找到从 s 到 v 的最短距离。
您可以复制 10 张图表来完成此操作。从单个副本开始（即同构 t G = (V, E)），除了 e1 从第一个副本移动到第二个副本。在第二个副本中（再次同构 t G = (V, E)），删除 e1 ，并让 e2 从第二个副本移动到第三个副本。等等。在结果图中，运行 任何算法从第一个副本中的 s 到第 10 个副本中的 e。
解释：凭直觉想象你的图G是画在二维sheet纸上的。影印它，这样你就有了 10 份，然后将它们堆叠成 10 份纸（不过想象一下，每两份之间有一点 space）。现在稍微更改图表，以便从第一个 sheet 上升到第二个 sheet 的唯一方法是通过边 e1 从底部 sheet 到第二个 sheet。从第二个 sheet 上升到第三个 sheet 的唯一方法是通过边 e2从第二个 sheet 到第三个 sheet，依此类推。你的问题是求最短路径，从最下面sheets对应的节点开始，到e[=43]对应的节点结束=] 在顶部 sheet.
要解决原始问题，只需对 E' 的所有可能排列重复此操作。请注意，有 10 个！ ~ 3.5e6 种可能性，并没有那么多。