在图中找到至少访问 X 个节点一次的最短电路 [英] Finding shortest circuit in a graph that visits X nodes at least once

问题描述

尽管我还是个初学者，但我喜欢解决与图相关的问题(最短路径、搜索等).最近我遇到了这样的问题:

Even though I'm still a beginner, I love solving graph related problems (shortest path, searches, etc). Recently I faced a problem like this :

给定一个具有 N 个节点和 E 个边的无向加权(无负值)图(两个节点之间最多有 1 个边，一条边只能放置在两个不同的节点之间)和一个 X 节点列表你必须访问，找到从节点 0 开始的最短路径，访问所有 X 个节点并返回节点 0.总是至少有一条路径连接任何两个节点.

Given a non-directed, weighted (no negative values) graph with N nodes and E edges (a maximum of 1 edge between two nodes, an edge can only be placed between two different nodes) and a list of X nodes that you must visit, find the shortest path that starts from node 0, visits all X nodes and returns to node 0. There's always at least one path connecting any two nodes.

限制为 1 <= N <= 40 000/1 <= X <= 15/1 <= E <= 50 000

Limits are 1 <= N <= 40 000 / 1 <= X <= 15 / 1 <= E <= 50 000

这是一个例子:

红色节点 (0) 应该是路径的起点和终点.您必须访问所有蓝色节点 (1,2,3,4) 并返回.这里的最短路径是:

The red node ( 0 ) should be the start and finish of the path. You must visit all blue nodes (1,2,3,4) and return. The shortest path here would be :

0 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0 总成本为 30

0 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0 with a total cost of 30

我想过使用 Dijkstra 来找到所有 X(蓝色)节点之间的最短路径，然后贪婪地选择最近的未访问 X(蓝色)节点，但它不起作用(在纸上提出 32 而不是 30).后来我也注意到，仅仅找到所有 X 节点对之间的最短路径需要 O(X*N^2) 时间，这对于这么多节点来说太大了.

I thought about using Dijkstra to find the shortest path between all X (blue) nodes and then just greedy picking the closest unvisited X (blue) node, but it doesn't work (comes up with 32 instead of 30 on paper). Also I later noticed that just finding the shortest path between all pairs of X nodes will take O(X*N^2) time which is too big with so much nodes.

我能找到的唯一电路是欧拉电路，它只允许访问每个节点一次(我不需要那个).这个问题可以用 Dijkstra 解决还是有其他算法可以解决这个问题?

The only thing I could find for circuits was Eulerian circuit that only allows visiting each node once (and I don't need that). Is this solveable with Dijkstra or is there any other algorithm that could solve this?

推荐答案

这是一个可能足够快的解决方案:
1) 从每个蓝色节点运行最短路径搜索算法(这可以在 O(X * (E log N)) 中完成)以计算成对距离.
2)构建一个只有零顶点和蓝色顶点(X + 1 个顶点)的新图.使用第一步计算的成对距离添加边.
3)新图足够小，可以对TSP使用动态规划解决方案(它的时间复杂度为O(X^2 * 2^X)).

Here is a solution which likely to be fast enough:
1)Run shortest path search algorithm from every blue node(this can be done in O(X * (E log N))) to compute pairwise distances.
2)Build a new graph with zero vertex and blue vertices only(X + 1 vertices). Add edges using pairwise distances computed during the first step.
3)The new graph is small enough to use dynamic programming solution for TSP(it has O(X^2 * 2^X) time complexity).

这篇关于在图中找到至少访问 X 个节点一次的最短电路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！