2
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ stackoverflow.com/q/39833023/781723 $\endgroup$
    – D.W. ♦
    Commented Aug 11 at 3:38
  • $\begingroup$ 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 $\endgroup$
    – D.W. ♦
    Commented Aug 12 at 21:37
  • $\begingroup$ 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? $\endgroup$
    – greybeard
    Commented Aug 13 at 14:16

1 Answer 1

Reset to default
0
$\begingroup$

The answer from StackOverflow:

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.

Now, as for efficiency: As @Codor points out, TSP is NP-hard and so is your variant of it, so you are not going to find a provably optimal, polynomial-time algorithm. However, there are still many, many good algorithms (both heuristic and exact) for TSP, and most of them should be suitable for your problem. (In general, DP is not the way to go for TSP.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.