在强制访问某些边缘的图形中找到最短路径，而其他人不是强制访问的最短路径 [英] find shortest path in a graph that compulsorily visits certain Edges while others are not compulsory to visit

问题描述

我有一个无向图，包含大约1000个节点和2000个边，一个起始节点和一个结束节点。我必须从开始节点遍历遍历所有强制边（约10个）的末端节点，而不必遍历所有顶点或节点。有没有一个简单的解决方案，像现有的图遍历算法中的一些小的变化？我该怎么做？

感谢您的帮助：

这个问题不同于查找图形中访问特定节点的最短路径，因为我的问题是关于强制边而不是顶点。

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

解决方法

为了解决相关问题，假设您有一个图形 G =（V，E），您必须以给定的顺序遍历 E'= 1，...，e ₁₀ >∈ E ，以及开始和结束节点 s，v∈ V 。您需要按给定的顺序使用 E'查找从 s到v 的最短距离。

您可以通过制作该图的10个副本来做到这一点。从一个副本开始（即，同构t = em =（V，E）），除了 e ₁ 从第一个副本移动到第二份。在第二个副本中（再次同构t G =（V，E）），移除 e ₁ ，并让 e ₂ 从第二个副本移动到第三个副本。等等在结果图中，运行任何算法从第一个副本的 s 到第10个副本的 e 。

解释：直观地想象你的图形 G 是绘制在一张2d的纸上。复印它，以便你有10份副本，并将它们堆叠成一堆10份文件（尽管想象它们之间有一定的空间）。现在改变一下图表，以便从第一张纸张开始到第二张纸张的唯一方式是通过从底部纸张开始的边缘 e ₁ 到第二张。从第二张纸到第三张纸的唯一方法是通过从第二张纸导向第三张纸的边 e ₂ ，依此类推。你的问题是找到从底部工作表上与 s 相对应的节点处开始的最短路径，并在顶部工作表上对应于 e 的节点处结束。

要解决原始问题，只需对 E'进行所有可能的排列组合。请注意，有10！ 〜3.5e6的可能性，这不是很多。

I have an undirected graph with about 1000 nodes and 2000 edges, a start node and an end node. I have to traverse from the start node to the end node passing through all the compulsory edges(which are about 10) while its not necessary to traverse through all the vertices or nodes. Is there an easy solution to this like some minor changes in the existing graph traversing algorithms? How do I do it?

Thanks for help.:)

This question is different from Find the shortest path in a graph which visits certain nodes as my question is regarding compulsory edges not vertices.

EDIT: The compulsory edges can be traversed in any order.

解决方案

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.

To solve the original problem, just repeat this with all possible permutations of E'. Note that there are 10! ~ 3.5e6 possibilities, which isn't all that much.

这篇关于在强制访问某些边缘的图形中找到最短路径，而其他人不是强制访问的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！