Thread: 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