Finding shortest circuit in a graph that visits X

问题:

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

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.

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

Here's an example :

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 with a total cost of 30

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.

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:

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).