无向图顶点集的最短路径访问
我有一张室内地图上的无向位置图。当给定一组顶点时，我要找到覆盖所有这些顶点的最短路径。图形包含52个顶点和150-250条边。
我能用什么最好的算法来找到最短的路径。请不要混淆这是一个旅行推销员的问题。它不需要覆盖所有节点，只需要覆盖给定的节点集。
共有1个答案
正如我所评论的，这是一个很难的问题，所以不要期望多项式时间算法。
但是，如果您正在寻找一种算法，可以在可接受的时间内计算出您提到的问题实例，这可能会起作用：
Let G(V,E) be the original graph, let N be the set of nodes that must be visited.
1. Compute the shortest-path matrix M for the entire graph (|V|x|V| matrix that contains
the length of the shortest path between each two nodes).
2. Generate a new graph G`, containing N alone, with the distances between each
two nodes taken from the shortest-path matrix M.
3. Solve the Minimum Weight Hamiltonian Path Problem on G`.
注意，这里“最难”的部分是第三部分，它需要指数级的时间。但如果组n不太大，则可以解决它：
- BruteForce算法可以让您在几秒钟内解决
n包含约11个节点的问题(O(n！）复杂度） - 动态编程可以让您在几秒钟内解决
n包含大约20个节点的问题(O(2^n*n^2)复杂度。
你基本上可以把任何解决最小权哈密顿路径问题的算法应用到第三部分，这些算法通常等价于TSP算法（这些问题的唯一区别是在TSP中你在访问所有其他节点后返回源节点）。
-
以下是消费税： 在某些图的问题中，顶点可以有权代替边的权或增加边的权。设Cv是顶点v的代价，C(x，y)是边(x，y)的代价。该问题涉及到在图G中寻找顶点a和顶点b之间的最便宜路径，路径的代价是该路径上遇到的边和顶点的代价之和。 (a)假设图中每条边的权重为零（而非边的代价为∞)，假设所有顶点1≤V≤n（即所有顶点的代价相同），Cv=1。给出一个求从a到b最便宜路径的高效算法及其时间复杂度。 (b
-
我们有一个边带正权的有向图G(V，E)，作为源顶点s，目标点T。此外，最短的s-t路径包括图中的每一个其他顶点。我需要计算s和t之间的交替最短路径距离，以防某些边e∈e被删除。我想设计一个O(e^2logV)算法，它计算图G\e中所有e∈e的最短S-T路径距离。最后的输出应该是一个大小为E的数组，其中edge E的条目应该包含G\E中最短的S-T路径距离。
-
在无向赋权图中寻找两个顶点之间的最短路径。还已知权重是小于log（logV）的整数，其中V是顶点的数量。使用贝尔曼-福特或Dijkstra算法很容易解决，但是有没有什么算法可以更快地解决呢？ 到目前为止，我一直在考虑使用BFS，将权重大于1的边划分成两个权重为1的边，但如果V是大数，就不是一个好主意。不，这不是我的家庭作业，我只是在想。
-
给定一些无向边加权图，什么算法可以用来找到从某个顶点v到另一个顶点w的最短路径？ 对于有向边加权图，可以使用Dijkstra的最短路径算法，但我使用的是无向图，所以它不起作用。 对于非边加权的图，可以使用广度优先搜索（BFS），但我使用的是边加权图，所以它不起作用。 既然它是无向和边加权的，一般最短路径法是什么？
-
下面的堆栈溢出问题 我尝试了在语句中使用两个重复的多个构造，但无法为每个起始顶点获得独立的。我也在使用平台，因此它限制了Gremlin的使用，其中不允许使用循环/脚本。所有gremlin查询必须以并由与链接在一起的命令组成 https://docs.aws.amazon.com/neptune/latest/userguide/access-graph-gremlin-differences.ht