I got the shortest path length of tsp by following this algorithm

How can I modify this algorithm to get the shortest path

def tsp_helper(W,i,S,mem):
    if S == 0:
        return 0
    elif mem[i][S] != None:
        return mem[i][S]
    else:
        mem[i][S] = float('infinity')
        for j in range(len(W)):
            if S & (1<<j) != 0:
                best = W[i][j]   tsp_helper(W,j,S^(1<<j),mem)
                if best < mem[i][S]:
                    mem[i][S] = best        
        return mem[i][S]
def tsp_memoized(W):
    mem = [[None]*(1<<len(W)) for _ in range(len(W))]
    return tsp_helper(W,0,(1<<len(W))-2,mem)

C = [[0,3,6,7],
    [5,0,2,3],
    [6,4,0,2],
    [3,7,5,0]]
print(tsp_memoized(C))

I'm trying to add a best_path list to include routing nodes

CodePudding user response：

You can store how you figured out each path weight as well as its value. This way, when you want to find a path, you can go one step back each time until you reach where you started.

The code would look something like this:

import sys

def tsp_helper(W,i,S,mem):
    if S == 0:
        return (0, None)
    elif mem[i][S] != None:
        return mem[i][S]
    else:
        mem[i][S] = (sys.float_info.max, None)
        for j in range(len(W)):
            if S & (1<<j) != 0:
                best = W[i][j]   tsp_helper(W,j,S^(1<<j),mem)[0]
                if best < mem[i][S][0]:
                    mem[i][S] = (best, j)        
        return mem[i][S]
def tsp_memoized(W):
    mem = [[None]*(1<<len(W)) for _ in range(len(W))]
    S = (1<<len(W))-2
    result = tsp_helper(W,0,S,mem)
    cur = result
    path = [0]
    while cur is not None:
        path.append(cur[1])
        S ^= (1<<cur[1])
        cur = mem[cur[1]][S]
    return result[0], path


C = [[0,3,6,7],
    [5,0,2,3],
    [6,4,0,2],
    [3,7,5,0]]
print(tsp_memoized(C))

Also, I think it's worth mentioning that you're currently calculating the Hamiltonian path and not the cycle.