What's a fast algorithm that can find a short path to traverse each node of a weighted undirected graph at least once?

Question

My problem is the following:

I have an undirected graph. Each edge has a cost (or weight). One of the nodes is labelled S. I want to start from S and visit every node at least once. Visiting a node multiple times is allowed. Travelling along an edge multiple times is allowed, although that would make the solution more expensive -- travelling an edge with cost of 3 twice will add 6 to the cost of the total path. The graph has some "dead-end" nodes, so sometimes we have to travel an edge more than once.

What is a fast algorithm to do this? Is this a well known problem?

What I'm looking for:

Reasonably fast -- The relative size of the graph we are talking about here is order of 40 - 50 nodes. So the algorithm hopefully won't take longer than 10 - 15 seconds.

Reasonably optimal -- I'm not looking for absolute optimality. Any interesting heuristic to guide the search so that the solution will be near optimal is good enough.

I will be writing this in python. So if you know of any python implementation of the algorithm, that's best.

Thanks for any help.

Answer 1

That is a version of the Travelling Salesman Problem, for which the wikipedia article has good overviews of various different heuristics.

The big difference between standard TSP and your algorithm is that TSP normally enforces only one visit per node, whereas you are allowing multiple visits. That problem was answered nicely in this SO question.

This guy documented his Python TSP solution, and this a pretty helpful discussion of generally how to implement graph stuff in Python.

Answer 2

Single-Source-Shortest-Path

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

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

However, if the graph contains negative edge weights, Bellman-Ford's Algorithm will find the optimal answer in $O(|V||E|)$ time, subject to the constraint that the graph does not contain negative-weight cycles.

All-Pairs-Shortest-Path

This is to find the shortest path between any two nodes $u,v$ in the graph. It can be solved by Floyd-Warshall's Algorithm in time $O(|V|^3).$ Similarly to the Bellman-Ford approach, the graph must not contain negative-weight cycles.

The reasoning for the negative-weight cycle constraint is that a shortest path could continually take the cycle and reduce its weight (as shown below).

Answer 3

Use Iterative Limited Depth First Search

see

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

Answer 4

A simple approach is to build the minimum spanning tree for your graph and do a (depth-first) walk over it, skipping nodes already visited.

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

Answer 5

EDIT 3: Nope, still looking

---

EDIT 2:

Here we go darksky, it has been way too long since i've done this haha

Djikstra's Algorithm

D's Algorithm finds the shortest distance from your starting node and every other node in a graph.

Here is a python implementation that looks reasonable to modify to work with your code:

Python Implementation

---

EDIT: As correctly pointed out in the comments, A* is (in one iteration) used for a single path. As such your requirement of visiting each node once is not met. I still think TSP is a much more complicated problem than the one you face as you are allowed to visit nodes > 1 time.

Original: A*

A* Wiki Article

I loved solving this problem back in college, enjoy!