Travelling salesman problem algorithm

Code:

#define OO 2000000;

int tsp(int **adjMatrix, int numberPoints)
{
	for (int i = 0; i < numberPoints; i++) 
		for (int j = 0; j < numberPoints; j++) 
			for (int k = 0; k < numberPoints; k++)
				if (adjMatrix[i][k] + adjMatrix[k][j] < adjMatrix[i][j])
					adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
	
	int min = OO;

	for (int i = 0; i < numberPoints; i++) 
		for (int j = 0; j < numberPoints; j++) 
			if (adjMatrix[i][j] + adjMatrix[j][i] < min)
				min = adjMatrix[i][j] + adjMatrix[j][i];

	return min;
}

I found this algorithm that solves the TSP problem. We give this function an adjacent matrix (a graph) and the number of points and it returns the minimal travel distance to visit all points (but only once each point).

I can't understand what this algorithm do. Someone knows the name of this algorithm or could explain me how it works?

Thank you,
Rafael Andreatta

I am not experienced at all with this stuff, nor have I ever used the algo.

but it looks something like this
Floyd–Warshall algorithm - Wikipedia, the free encyclopedia

Are you sure it solves the TSP problem? It looks a lot more like "find the edge in the graph with least cost, and return twice that value".

@rodrigorules

Thank you for the link, it will help me...

@tabstop

Hum, I think I was wrong, it doesn't solve the TSP... But what it solves then? In wikipedia it says:

In computer science, the Floyd–Warshall algorithm (sometimes known as the WFI Algorithm or Roy–Floyd algorithm) is a graph analysis algorithm for finding shortest paths in a weighted, directed graph. A single execution of the algorithm will find the shortest paths between all pairs of vertices.

But if I do the Dijkstra's algorithm for each vertex in the graph won't I get the same result?

I'm confused about this ;S

If you run Dijkstra's algorithm for every pair of vertices, you'll get much the same result, yes. (Dijkstra's algorithm also produces the shortest path; this algorithm just tells us the length of the shortest path.)

@tabstop

Hum, ok. But on a test I'm studying for, there's a problem such that: The user inputs data telling me the number of points, the connections between these points (and it's distance) then I need to find the shortest distance that I need to travel to visit all points. But there are some restrictions:

A) The travel must start and end at the same point
B) We must visit each point once
C) We must visit at least 2 points
D) The connections are unidimentional so we can only travel at one direction on each connection

What I'm not understanding is: the correct answer to that problem is to use the algorithm that I posted in this thread. But this algorithm doesn't solve the TSP. But this problem on the test isn't the same as the TSP? If I can solve this with Floyd–Warshall algorithm I can also solve using Dijkstra's algorithm for each point, but how I would do that?

Thank you again

the correct answer to that problem is to use the algorithm that I posted in this thread.

You say that, but I'm not convinced.

Originally Posted by Taturana182

@tabstop

Hum, ok. But on a test I'm studying for, there's a problem such that: The user inputs data telling me the number of points, the connections between these points (and it's distance) then I need to find the shortest distance that I need to travel to visit all points. But there are some restrictions:

A) The travel must start and end at the same point
B) We must visit each point once
C) We must visit at least 2 points
D) The connections are unidimentional so we can only travel at one direction on each connection

What I'm not understanding is: the correct answer to that problem is to use the algorithm that I posted in this thread. But this algorithm doesn't solve the TSP. But this problem on the test isn't the same as the TSP? If I can solve this with Floyd–Warshall algorithm I can also solve using Dijkstra's algorithm for each point, but how I would do that?

Thank you again

Yes, running Dijkstra for each node will return the same results as Floyd-Warshall. However, Floyd-Warshall will return it faster, and the algorithm is fairly easy to implement.
I don't understand point B and C though; they kind of conflict with each other in my opinion. You need to visit each point exactly once, and you must visit at least 2 points? Well, obviously, if you need to visit all points...

Floyd-Warshall has a complexity of O(n^3), whereas solving a general TSP has a complexity of O(2^n) (or somewhat along those lines), unless P == NP. So, no, floyd-warshall definitely can't be used to solve the TSP problem unless maybe it's a very specific case. So if there are constraints on the problem, write them here as well.

Yes, running Dijkstra for each node will return the same results as Floyd-Warshall.

Well, Dijkstra's Algorithm only works for Digraphs with positive weights, whereas Warshall's Algorithm finds all shortest paths for a Digraph with conservative weights, rather like Bellman-Ford for all pairs of vertices (iirc, it builds a potential using Bellman-Ford and utilizes the "reduced costs" of edges to compute the actual shortest-path-trees)

(conservative weights means: no cycles of negative length; finding a shortest path in a graph with arbitrary weights (i.e., negative cycles may occur) is NP-complete, seen e.g. via reduction of the Hamilton problem).

PS
Your problem is also NP-Complete (you search a Hamilton cycle, and it is NP-hard to decide whether such a path exists in a given graph), so you won't find a solution with any trivial algorithm for, say, more than 30 vertices. (Naive TSP takes O(n!), 30! means something along the lines "you require more time than the universe will exist". Of course, TSP is very well studied, and some facets of the polyhedron are known. Solving relaxations and using the results as bounds for a Branch&Bound algorithm, tours for as much as 20000 vertices have been found, but trust me, that isn't something you want to implement yourself, except perhaps if you are a professor for combinatorics with ambitions in integer optimization, in which case you wouldn't have mistaken the Warshall algorithm for a TSP solution - no offense).

Originally Posted by assertion

(conservative weights means: no cycles of negative length; finding a shortest path in a graph with arbitrary weights (i.e., negative cycles may occur) is NP-complete, seen e.g. via reduction of the Hamilton problem).

Fair points, although I'm not sure I agree with this one, though I might be wrong. The problem is that if negative cycles exist, there is no shortest path between most nodes because it is minus infinity. It's easy to see: go to the cycle and repeat it an infinite number of times, then finish the tour (if the path exists).
So all you need to do is run Floyd-Warshall, decide if a negative cycle exists or not and if so, you need to decide which two nodes have a path between them where any node in the negative cycle is part of it. If so, the length is minus infinity. If not, it's the regular floyd-warshall length...

Dijkstra's algorithm - Wikipedia, the free encyclopedia
Dijkstras algorithm... with a code there already, so...

[off topic: minimal path length in an arbitrary graph is NP-complete]
(a) we define a path to have no self-intersections. This way, a minimal length path is defined.
(b) Containment in NP is obvious.
(c) Completeness is seen by reduction of the Hamilton problem: given a graph G = (V, E), decide whether G is Hamiltonian. Reduction is done as follows: construct a graph G', which is complete, and set all weights of edges to -1 for which a corresponding edge was in G, this takes O(|V|^2). All other edges are set to 0. Now we seek, given our general-purpose shortest-path algorithm, a shortest path from an arbitrary vertex v to itself. The weight of this path is -|V| <=> G was Hamiltonian. QED.

Originally Posted by assertion

[off topic: minimal path length in an arbitrary graph is NP-complete]
(a) we define a path to have no self-intersections. This way, a minimal length path is defined.
(b) Containment in NP is obvious.
(c) Completeness is seen by reduction of the Hamilton problem: given a graph G = (V, E), decide whether G is Hamiltonian. Reduction is done as follows: construct a graph G', which is complete, and set all weights of edges to -1 for which a corresponding edge was in G, this takes O(|V|^2). All other edges are set to 0. Now we seek, given our general-purpose shortest-path algorithm, a shortest path from an arbitrary vertex v to itself. The weight of this path is -|V| <=> G was Hamiltonian. QED.

Ahh, yes, in that case, even though I don't see any reason why a path should have no self-intersections. I mean, let's say there's a wormhole through which you can travel back in time 1 year. Then the fastest path to some other location is to fly through the wormhole. You end up one year in the past. Then you fly through the wormhole again. Another year. Obviously, you can arrive at your location when the earth was created.
Of course, this is a theoretical case only, but we require computers to solve theoretical cases sometimes. And I've never seen your restriction anywhere, really.

But yes, assuming your restriction, you're right.

[Really off-topic - definitions of paths and walks]
A walk is a path in which self-intersections are allowed, a path does not have self-intersections. At least that is the definition in "Combinatorial Optimization" (the rest of my textbooks concerning that matter are in German, and we call them "Pfad" and "Weg", resectively). The TSP is defined to be a cycle, i.e. a closed path, *not* a closed walk. And if you define paths as walks, then you will get a problem defining longest paths as well (shortest and longest walks are indeed not well-defined; paths are). Note that for positive weights, the longest path problem is also NP-complete.

Originally Posted by assertion

[Really off-topic - definitions of paths and walks]
A walk is a path in which self-intersections are allowed, a path does not have self-intersections. At least that is the definition in "Combinatorial Optimization" (the rest of my textbooks concerning that matter are in German, and we call them "Pfad" and "Weg", resectively). The TSP is defined to be a cycle, i.e. a closed path, *not* a closed walk. And if you define paths as walks, then you will get a problem defining longest paths as well (shortest and longest walks are indeed not well-defined; paths are). Note that for positive weights, the longest path problem is also NP-complete.

[Extremely off-topic - defintiion of paths and simple paths ;-)]
Wikipedia disagrees:
Path (graph theory) - Wikipedia, the free encyclopedia
It says a "simple path" is a path with no repeated vertices. But I guess it all depends on who uses what definition, which tend to cause a lot of trouble in many areas of science..

I guess we're both right, just according to different (but probably both accepted) definitions.