Modify Held-Karp TSP algorithm so we do not need to go back to the origin

Question

I have to solve a problem where I had to find the shortest path to link all points starting from a distance matrix. It's almost like a Traveling Salesman Problem except I do not need to close my path by returning to the starting point. I found the Held-Karp algorithm (Python) that solves the TSP very well but always computes distances returning to the starting point. So now it leaves me with 3 questions :

1. Could at least one situation have a different result if I modify my function not to get back to the starting point?
2. If the answer to 1 is yes, how could I alter my held_karp() function to fit my needs?
3. It there is no way in 2, what should I look for next?

I have translated the held_karp() function from Python to PHP, and for my solution I'd be happy to use either language.

function held_karp($matrix) {
    $nb_nodes = count($matrix);

    # Maps each subset of the nodes to the cost to reach that subset, as well
    # as what node it passed before reaching this subset.
    # Node subsets are represented as set bits.
    $c = [];

    # Set transition cost from initial state
    for($k = 1; $k < $nb_nodes; $k++) $c["(".(1 << $k).",$k)"] = [$matrix[0][$k], 0];

    # Iterate subsets of increasing length and store intermediate results
    # in classic dynamic programming manner
    for($subset_size = 2; $subset_size < $nb_nodes; $subset_size++) {
        $combinaisons = every_combinations(range(1, $nb_nodes - 1), $subset_size, false);
        foreach($combinaisons AS $subset) {
            # Set bits for all nodes in this subset
            $bits = 0;
            foreach($subset AS $bit) $bits |= 1 << $bit;

            # Find the lowest cost to get to this subset
            foreach($subset AS $bk) {
                $prev = $bits & ~(1 << $bk);

                $res = [];
                foreach($subset AS $m) {
                    if(($m == 0)||($m == $bk)) continue;
                    $res[] = [$c["($prev,$m)"][0] + $matrix[$m][$bk], $m];
                }
                $c["($bits,$bk)"] = min($res);
            }
        }
    }

    # We're interested in all bits but the least significant (the start state)
    $bits = (2**$nb_nodes - 1) - 1;

    # Calculate optimal cost
    $res = [];
    for($k = 1; $k < $nb_nodes; $k++) $res[] = [$c["($bits,$k)"][0] + $matrix[$k][0], $k];
    list($opt, $parent) = min($res);

    # Backtrack to find full path
    $path = [];
    for($i = 0; $i < $nb_nodes - 1; $i++) {
        $path[] = $parent;
        $new_bits = $bits & ~(1 << $parent);
        list($scrap, $parent) = $c["($bits,$parent)"];
        $bits = $new_bits;
    }

    # Add implicit start state
    $path[] = 0;

    return [$opt, array_reverse($path)];
}

In case you need to know how the every_combinations() function works

function every_combinations($set, $n = NULL, $order_matters = true) {
    if($n == NULL) $n = count($set);
    $combinations = [];
    foreach($set AS $k => $e) {
        $subset = $set;
        unset($subset[$k]);
        if($n == 1) $combinations[] = [$e];
        else {
            $subcomb = every_combinations($subset, $n - 1, $order_matters);
            foreach($subcomb AS $s) {
                $comb = array_merge([$e], $s);
                if($order_matters) $combinations[] = $comb;
                else {
                    $needle = $comb;
                    sort($needle);
                    if(!in_array($needle, $combinations)) $combinations[] = $comb;
                }
            }
        }
    }
    return $combinations;
}

Answer 1

Yes, the answer can be different. For instance, if the graph has 4 vertices and the following undirected edges:

1-2 1
2-3 1
3-4 1
1-4 100
1-3 2
2-4 2

The optimal path is 1-2-3-4 with a weight 1 + 1 + 1 = 3, but the weight of the same cycle is 1 + 1 + 1 + 100 = 103. However, the weight of the cycle 1-3-4-2 is 2 + 1 + 2 + 1 = 6 and the weight of this path is 2 + 1 + 2 = 5, so the optimal cycle and the optimal path are different.

If you're looking for a path, not a cycle, you can use the same algorithm, but you don't need to add the weight of the last edge to the start vertex, that is

for($k = 1; $k < $nb_nodes; $k++) $res[] = [$c["($bits,$k)"][0] + $matrix[$k][0], $k];

should be for($k = 1; $k < $nb_nodes; $k++) $res[] = [$c["($bits,$k)"][0], $k];