我有一个带有大约1000个节点和2000个边的无向图，一个起始节点和一个结束节点 . 我必须从起始节点遍历遍历所有强制边（大约10）的结束节点，而不必遍历所有顶点或节点 . 是否有一个简单的解决方案，就像现有的图遍历算法中的一些细微变化？我该怎么做？
感谢帮助 . ：）
这个问题与Find the shortest path in a graph which visits certain nodes不同，因为我的问题是关于强制边而不是顶点 .
编辑：强制边可以任何顺序遍历 .
我有一个带有大约1000个节点和2000个边的无向图，一个起始节点和一个结束节点 . 我必须从起始节点遍历遍历所有强制边（大约10）的结束节点，而不必遍历所有顶点或节点 . 是否有一个简单的解决方案，就像现有的图遍历算法中的一些细微变化？我该怎么做？
感谢帮助 . ：）
这个问题与Find the shortest path in a graph which visits certain nodes不同，因为我的问题是关于强制边而不是顶点 .
编辑：强制边可以任何顺序遍历 .
1 回答
要从一个相关的问题开始，假设你有一个图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是在2d纸上绘制的 . 复印它，这样你就可以复印10份，并将它们堆叠成10张纸（尽管如此，想象它们之间有一点空间） . 现在稍微更改图形，以便从第一张纸到达第二张纸的唯一方法是通过从底部纸张到第二张纸张的边缘e1 . 从第二张纸到第三张纸的唯一方法是通过从第二张纸到第三张纸的边缘e2，依此类推 . 您的问题是找到从与底部页面上的s对应的节点开始的最短路径，并在顶部工作表上与e对应的节点处结束 .
要解决原始问题，只需用E'的所有可能排列重复此问题 . 注意有10个！ ~3.5e6的可能性，这并不是那么多 .