path finding - Minimum cost cycle on complete graph -

path finding - Minimum cost cycle on complete graph -

i have complete graph undirected, weighted edges , need find lowest cost cycle through subset of graph nodes. unlike in travelling salesman, any node can visited more once , not all nodes need visited, , cost mean path should have smallest sum of traversed border weights.

for example, here graph in adjacency matrix form:

b c d 0 3 4 5 b 3 0 2 4 c 4 2 0 1 d 5 4 1 0

where weight of each border used each element. cycles starting , ending @ a , including [b,d] like

[a,b,d,a] -> 3+4+5 = 12 [a,b,d,b,a] -> 3+4+4+3 = 14 [a,b,c,d,c,a] -> 3+2+1+1+4 = 11

is there optimal algorithm this, or heuristic one?

cycles starting , ending @ a , including [b,d] means cycle must visit nodes a,b,d. [a,b,d,a] = [b,d,a,b] (cycles right). problem called k-tsp. see here. hard implement , may not looking for.

so give simpler way. first build shortest cycle passes through these nodes. replace each border smallest path between 2 nodes. think reasonable, leave out optimality. here steps :

v=nodes e=edges , m=must-visit nodes. create cycle c running tsp on m (without using other nodes), adding border create cycle. now using nodes v. each border uv in the c, do: find shortest path w between u , v using dijsktra's algorithm (should no negative cycle in graph). replace uv w.

path-finding graph-traversal