What is a quick algorithm that can find a short way to intersect each node of a weighted undirected graph at least once?

Question

My problem is this:

I have an undirected graph. Each edge has a cost (or weight). One of the nodes is labeled S. I want to start with S and visit each node at least once. Allowed to visit node several times. Movement along the edge is allowed several times, although this will make the solution more costly - moving along the edge with a cost of 3 will add 6 twice to the cost of the entire path. There are several “dead end” nodes on the graph, so sometimes we have to move around the edge more than once.

What is a fast algorithm for this? Is this a well-known issue?

What I'm looking for:

Quite quickly - the relative size of the graph that we are talking about is about 40-50 nodes. Therefore, the algorithm, I hope, does not take more than 10-15 seconds.

Reasonably optimal - I'm not looking for absolute optimality. Any interesting heuristics to guide the search so that the solution is almost optimal, good enough.

I will write this in python. Therefore, if you know about any python algorithm implementation, this is best.

Thanks for any help.

Answer 1

This is a version of the traveling salesman problem for which the wikipedia article contains good reviews of various heuristics.

The big difference between the standard TSP and your algorithm is that TSP usually provides only one visit per node, while you allow multiple visits. This problem was satisfied with this .

This guy has documented his PSP TSP solution and this is a pretty useful discussion about how to implement graphical material in Python.

Answer 2

Use Iterative Limited Depth First Search

cm

http://en.wikipedia.org/wiki/Depth-limited_search

Answer 3

A simple approach is to build a minimum spanning tree for your graph and go through it (in depth), skipping the nodes that have already been visited.

This is proven no more than twice as long as the optimal TSP path. You can definitely deal better with heuristics, but it's a starter (and it's easy to implement).

Answer 4

Single-Source-Shortest Path

If you have node $ s $ and you want to find a short path to node $ t $.

If the graph has non-negative edge weights, Dijkstra Algorithm will find the optimal answer in time $ O (| E | + | V | \ log | V |) $.

However, if the graph contains negative edge weights, the Bellman-Ford algorithm will find the optimal answer in $ O (| V || E |) $ time, provided that the graph does not contain cycles of negative weight.

All-steam-shortest way

This is finding the shortest path between any two nodes $ u, v $ in the graph. It can be solved using the Floyd-Warsall algorithm in time $ O (| V | ^ 3). $ Like the Bellman-Ford method, the chart should not contain cycles of negative weight.

The rationale for limiting negative weight is that the shortest path can continuously go through the cycle and reduce its weight (as shown below).

Answer 5

EDIT 3: No, still looking

---

EDIT 2:

Here we go darksky, it has been too long since I made it haha

Jikstra Algorithm

D The algorithm finds the shortest distance from your starting node and any other node in the graph.

Here is a python implementation that is reasonably modified to work with your code:

Python implementation

---

EDIT: As stated in the comments, A * (in one iteration) is used for one path. Thus, your requirement to visit each node once fails. I still think that TSP is a much more complicated problem than the one you are facing, as you are allowed to visit sites> 1 time.

Original: A *

A * Wiki article

I liked solving this problem back in college, enjoy!