# Shortest path to all nodes from a center point, repeats allowed

I'm trying to create an algorithm to figure out a path visiting every single node in a graph (undirected and unweighted) - similar to the traveling salesman problem, but I can visit a node multiple times. I can't use brute force mainly because there's 299 nodes.

Furthermore, this is special because every point is connected to every other point - there's 44551 paths. I've seen people recommending the Floyd-Warshall algorithm to help optimize each node pair connection, but I don't think it applies in this case because each point is already connected to every other point.

If anyone can tell me how to start, that would be great! Or if someone can help me modify an existing TSP algorithm to solve this problem. Also, Python is the language I'm using, mainly because of the networkx library

Edit: forgot to mention that I don't need to only make roads to the nodes - for example, if nodes 1, 2, and 3 form an equilateral triangle, TSP says the shortest distance is to go from 1-2-3-1 along the edges, but I can use Fermat Points to make the distance smaller (3 units vs sqrt3 units) - sorry if this sounds a bit incoherent

• stackoverflow.com/q/39833023/781723
– D.W.
Commented Aug 11 at 3:38
• Please don't use "Edit: [more stuff]". Instead, revise your question so it reads well for someone who encounters it for the first time, and contains all information in the logical order. See cs.meta.stackexchange.com/q/657/755
– D.W.
Commented Aug 12 at 21:37
• On first take, I read unweighted as unit distance/cost - but then, where was the problem? So if every edge has it's own length, how shall I interpret unweighted? Using additional points, this does not read graph - is it planar geometry? Commented Aug 13 at 14:16

The typical approach is to create a distance matrix that gives the shortest-path distance between any two nodes. So d(i,j) = shortest path (following the edges of the network) from i to j. This can be done using Dijkstra's algorithm.
Now just solve a classical TSP with distances d(i,j). Your TSP doesn't "know" that the actual route followed might involve visiting a node multiple times. At the same time, it will ensure that the vehicle stops at every node.