How to modify this Held-Karp algorithm to search for Hamiltonian path instead of cycle?

Question

I implemented Held-Karp in Java following Wikipedia and it gives the correct solution for total distance of a cycle, however I need it to give me the path (it doesn't end on the same vertex where is started). I can get path if I take out the edge with largest weight from the cycle, but there is a possibility that 2 different cycles have same total distance, but different maximum weight, therefore one of the cycles is wrong.

Here is my implementation:

//recursion is called with tspSet = [0, {set of all other vertices}]

private static TSPSet recursion (TSPSet tspSet) {
    int end = tspSet.endVertex;
    HashSet<Integer> set = tspSet.verticesBefore;

    if (set.isEmpty()) {
        TSPSet ret = new TSPSet(end, new HashSet<>());
        ret.secondVertex = -1;
        ret.totalDistance = matrix[end][0];
        return ret;
    }

    int min = Integer.MAX_VALUE;
    int minVertex = -1;
    HashSet<Integer> copy;

    for (int current: set) {
        copy = new HashSet<>(set);
        copy.remove(current);

        TSPSet candidate = new TSPSet(current, copy);

        int distance = matrix[end][current] + recursion(candidate).totalDistance;

        if (distance < min) {
            min = distance;
            minVertex = current;
        }
    }

    tspSet.secondVertex = minVertex;
    tspSet.totalDistance = min;

    return tspSet;
}

class TSPSet {
    int endVertex;
    int secondVertex;
    int totalDistance;
    HashSet<Integer> verticesBefore;

    public TSPSet(int endVertex, HashSet<Integer> vertices) {
        this.endVertex = endVertex;
        this.secondVertex = -1;
        this.verticesBefore = vertices;
    }
}

Answer 1

Problem with current approach

Consider this graph:

The shortest path visiting all vertices (exactly once each) is of length 3, but the shortest cycle is 1+100+200+300, which is 301 even if you remove the maximum weight edge.

In other words, it is not correct to construct the shortest path by deleting an edge from the shortest cycle.

Suggested approach

An alternative approach to convert your cycle algorithm into a path algorithm is to add a new node to the graph which has a zero cost edge to all of the other nodes.

Any path in the original graph corresponds to a cycle in this graph (the start and end points of the path are the nodes that the extra node connects to.

Answer 2

You can slightly alter the dynamic programming state.

Let the path start in a node S. Let f(subset, end) be the optimal cost of the path that goes through all the vertices in the subset and ends in the end vertex (S and end must always be in the subset). A transition is just adding a new vertex V not the subset by using the end->V edge.

If you need a path that ends T, the answer is f(all vertices, T).

A side note: what you're doing now is not a dynamic programming. It's an exhaustive search as you do not memoize answers for subsets and end up checking all possibilities (which results in O(N! * Poly(N)) time complexity).