Graph Algorithm : Similar to TSP -

i want solve problem similar tsp( travelling salesman problem). have n ( n > 0, n < 20 ) nodes , must visit nodes. cost between nodes equal. can visit node unlimited times. want find more 1 path , cost have not restriction. tell me effective algorithms problem?

here solution works weighted graph.

first, naive solution, enumerating.

it works in o(n!) because there (n-1)! hamiltonian paths, , need o(n) check each one.

there better algorithm, dynamic programming in o(n*2^n)

define state following: x node, , s set of nodes containing x:

w[s][x] = weight of shortest path start @ node x, , goes through node in set s, , finishes @ 0.

note 0 not belongs s.

s = {x} basic case: w[s][x] = weight(w,0)

then recursion formula:

if s larger than, {x}, iterate on possible next step y

w[s][x] = min(weight(x,y) + w[s\x][y] y in s\x) 

this algorithm output 1 optimal path.