CODEWITHSUNDEEP
pythongraphnetworkxtraveling-salesman
lode
lode

Reputation: 564

python tsp travelling salesman undirected graph

In other posts Networkx was suggested as "my friend". But there doesn't seem to be a ready to use function for a certain solution for the TSP problem. i.e. Creating undirected graphs in Python

I have an undirected graph, the suggested solutions are all related to directed graphs, and I want to know a short tour to visit all nodes using the available edges.

(also, the tsp with directed graphs I could not find in the documentation of networkx)

Does anybody did something like this for an undirected graph or should I modify solutions for directed graphs with infinit costs for unconnected nodes?

edit: I am learning: Actually, as the graph is unweighted (or 'all weights' are the same), and not every node is connected to all other nodes, I just need to find a cycle in the graph containing all the nodes. When that cycle does not exist, nodes may be repeated (so, it is not a cycle anymore...). There are no isolated groups (there is a path from each node to another). I think that this is not the salesman problem?!

Thanks for your feedback so far (when milliseconds start to matter, I will install a photofinish :) )

Upvotes: 4

Views: 3965

Answers (1)

chepner
chepner

Reputation: 530833

If you already have code for directed graphs, I would just convert your undirected graph. Replace each undirected edge with two directed edges, one in each direction, preserving the edge weight.

Upvotes: 2

Related Questions