找到图中强制访问某些边而其他边不强制访问的最短路径

我有一个无向图，约有 1000 个节点和 2000 个边、一个起始节点和一个结束节点。我必须从起始节点遍历到结束节点，穿过所有强制边（大约10条），而不必遍历所有顶点或节点。有没有一个简单的解决方案，比如对现有的图遍历算法进行一些小的改变？我该怎么做？

感谢帮助。：）

这个问题不同于查找图中访问某些节点的最短路径 https://stackoverflow.com/questions/222413/find-the-shortest-path-in-a-graph-which-visits-certain-nodes因为我的问题是关于强制边而不是顶点。

编辑：强制边可以按任何顺序遍历。

To start with a related problem, say you have a graph G = (V, E), 10 specific edges you must traverse in a given order E' = 1, ..., e₁₀ > ∈ E, and a start and end nodes s, v ∈ V. You need to find the shortest distance from s to v using E' in the given order.

You could do this by making 10 copies of the graph. Start with a single copy (i.e., isomorphic t G = (V, E)), except that e₁ moves from the first copy to the second copy. In the second copy (again isomorphic t G = (V, E)), remove e₁, and have e₂ move from the second copy to the third copy. Etc. In the resulting graph, run any algorithm to get from s in the first copy to e in the 10th copy.

Explanation: imagine intuitively that your graph G is drawn on a 2d sheet of paper. photocopy it so that you have 10 copies, and stack them up to a pile of 10 papers (imagine them with a bit of space between each two, though). Now change the graphs a bit so that the only way to go up to the second sheet, from the first sheet, is through an edge e₁ leading from the bottom sheet to the second sheet. The only way to go up to the third sheet, from the second sheet, is through an edge e₂ leading from the second sheet to the third sheet, and so on. You problem is to find the shortest path starting at the node corresponding to s on the bottom sheet, and ending at the node corresponding to e on the top sheet.

要解决原始问题，只需用所有可能的排列重复此操作E'。请注意，有 10 个！ ~ 3.5e6 种可能性，这并不是那么多。