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

i have solve problem had find shortest path link points starting distance matrix. it's traveling salesman problem except not need close path returning starting point. found held-karp algorithm (python) solves tsp computes distances returning starting point. leaves me 3 questions :

1. could @ least 1 situation have different result if modify function not starting point?
2. if answer 1 yes, how alter held_karp() function fit needs?
3. it there no way in 2, should next?

i have translated held_karp() function python php, , solution i'd happy use either language.

function held_karp($matrix) {     $nb_nodes = count($matrix);      # maps each subset of nodes cost reach subset,     # node passed before reaching subset.     # node subsets represented set bits.     $c = [];      # set transition cost initial state     for($k = 1; $k < $nb_nodes; $k++) $c["(".(1 << $k).",$k)"] = [$matrix[0][$k], 0];      # iterate subsets of increasing length , 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 $subset) {             # set bits nodes in subset             $bits = 0;             foreach($subset $bit) $bits |= 1 << $bit;              # find lowest cost subset             foreach($subset $bk) {                 $prev = $bits & ~(1 << $bk);                  $res = [];                 foreach($subset $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 bits 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 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 need know how every_combinations() function works

function every_combinations($set, $n = null, $order_matters = true) {     if($n == null) $n = count($set);     $combinations = [];     foreach($set $k => $e) {         $subset = $set;         unset($subset[$k]);         if($n == 1) $combinations[] = [$e];         else {             $subcomb = every_combinations($subset, $n - 1, $order_matters);             foreach($subcomb $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; } 

yes, answer can different. instance, if graph has 4 vertices , following undirected edges:

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

the optimal path 1-2-3-4 weight 1 + 1 + 1 = 3, weight of same cycle 1 + 1 + 1 + 100 = 103. however, weight of cycle 1-3-4-2 2 + 1 + 2 + 1 = 6 , weight of path 2 + 1 + 2 = 5, optimal cycle , optimal path different.

if you're looking path, not cycle, can use same algorithm, don't need add weight of last edge start vertex, is

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

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