Travelling salesman problem algorithm

This is a discussion on Travelling salesman problem algorithm within the C++ Programming forums, part of the General Programming Boards category; Code: #define OO 2000000; int tsp(int **adjMatrix, int numberPoints) { for (int i = 0; i < numberPoints; i++) for ...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Posts
    4

    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
    Last edited by Salem; 03-22-2010 at 01:09 PM. Reason: Use proper code tags

  2. #2
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    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

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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".

  4. #4
    Registered User
    Join Date
    Mar 2010
    Posts
    4
    @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

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.)

  6. #6
    Registered User
    Join Date
    Mar 2010
    Posts
    4
    @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

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  8. #8
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by Taturana182 View Post
    @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.
    Last edited by EVOEx; 03-22-2010 at 04:48 AM.

  9. #9
    Registered User
    Join Date
    Mar 2010
    Posts
    18
    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).
    Last edited by assertion; 03-22-2010 at 02:22 PM.

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by assertion View Post
    (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...

  11. #11
    Registered User
    Join Date
    Mar 2010
    Location
    Norway
    Posts
    25
    Dijkstra's algorithm - Wikipedia, the free encyclopedia
    Dijkstras algorithm... with a code there already, so...

  12. #12
    Registered User
    Join Date
    Mar 2010
    Posts
    18
    [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.

  13. #13
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by assertion View Post
    [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.

  14. #14
    Registered User
    Join Date
    Mar 2010
    Posts
    18
    [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.

  15. #15
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by assertion View Post
    [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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. what is the algorithm in this problem..
    By cfan in forum C Programming
    Replies: 2
    Last Post: 08-04-2009, 12:52 PM
  2. data mamgment problem (algorithm)
    By cfan in forum C Programming
    Replies: 0
    Last Post: 08-02-2009, 01:07 PM
  3. Help with grid problem (dynamic programming)
    By scp89 in forum C Programming
    Replies: 15
    Last Post: 05-07-2009, 01:16 PM
  4. Simple algorithm problem
    By stodd04 in forum C Programming
    Replies: 11
    Last Post: 03-04-2005, 11:08 AM
  5. algorithm problem
    By cdonlan in forum C++ Programming
    Replies: 3
    Last Post: 02-10-2005, 09:16 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21