Solution to Travelling Salesman Problem

10
   0  583  584  201  291  526  337  327  180  304
 583    0 1030  633  854   90  389  353  405  638
 584 1030    0  420  362 1010  645  892  712  860
 201  633  420    0  254  601  277  475  293  504
 291  854  362  254    0  807  528  617  463  516
 526   90 1010  601  807    0  384  269  347  554
 337  389  645  277  528  384    0  389  247  570
 327  353  892  475  617  269  389    0  184  286
 180  405  712  293  463  347  247  184    0  325
 304  638  860  504  516  554  570  286  325    0

<br />
/*<br />
+-------Program to solve travelling salesman problem------------------+<br />
| by:                                                                 |<br />
| 								      |<br />
| Omkar Joshi                                                         |<br />
| 21 Male                                                             |<br />
| Mubai,India.                                                        |<br />
|                                                                     |<br />
| efficiency: O(n^4)                                                  |<br />
| optimality: I think yes!!!!!!                                       |<br />
| but still under test for different graphs                           |<br />
| so PLEASE:::send me the test cases along with the optimal solution  |<br />
| where my algorithm fails to give the optimal solution.              |<br />
| Free to use and/or distribute for non-commercial purposes.          |<br />
+---------------------------------------------------------------------+<br />
*/<br />
/*<br />
example:<br />
	  2<br />
    [0]-------[1]<br />
     | \4     /|<br />
     |	 \  /  |<br />
    3|    /\   |3<br />
     | 6/    \ |<br />
    [3]-------[2]<br />
	  1<br />
<br />
    inputs:<br />
    infinity:999<br />
    no. of cities: 4<br />
    no. of paths:6<br />
<br />
	  S D Dist<br />
    path0:0 1 2<br />
    path0:0 2 4<br />
    path0:0 3 3<br />
    path0:1 2 3<br />
    path0:1 3 6<br />
    path0:2 3 1<br />
*/<br />
<br />
#include<stdio.h><br />
#include<stdlib.h><br />
#define ALL -1<br />
#define MAXCITIES 2000<br />
<br />
enum BOOL{FALSE,TRUE};<br />
long*visited;//visited nodes set here<br />
long*min_circuit;//min inner circuit for given node as start node at position indexed 0<br />
long*ham_circuit;//optimal circuit with length stored at position indexed 0<br />
long min_circuit_length;//min circuit lenth for given start node<br />
<br />
int n;//city count<br />
long matrix[MAXCITIES][MAXCITIES];//nondirectional nXn symmetric matrix<br />
//to store path distances as sourceXdestination<br />
long INFI;// INFINITY value to be defined by user<br />
<br />
// function resets minimum circuit for a given start node<br />
//with setting its id at index 0 and setting furthr node ids to -1<br />
void reset_min_circuit(int s_v_id)<br />
{<br />
	min_circuit[0]=s_v_id;<br />
	for(int i=1;i<n;i++)	min_circuit[i]=-1;<br />
}<br />
<br />
// marks given node id with given flag<br />
// if id==ALL it marks all nodes with given flag<br />
void set_visited(int v_id,BOOL flag)<br />
{<br />
	if(v_id==ALL)	for(int i=0;i<n;i++)	visited[i]=flag;<br />
	else		visited[v_id]=flag;<br />
}<br />
<br />
// function sets hamiltonion circuit for a given path length<br />
//with setting it at index 0 and setting furthr nodes from current min_circuit<br />
void SET_HAM_CKT(long pl)<br />
{<br />
	ham_circuit[0]=pl;<br />
	for(int i=0;i<n;i++)       ham_circuit[i+1]=min_circuit[i];<br />
	ham_circuit[n+1]=min_circuit[0];<br />
}<br />
<br />
//function sets a valid circuit by finiding min inner path for a given<br />
//combination start vertex and next vertex to start vertex such that<br />
// the 2nd vertex of circuits is always s_n_v and start and dest node is<br />
//always s_v for all possible values of s_n_v, and then returns the<br />
// valid circuit length for this combination<br />
<br />
long get_valid_circuit(int s_v,int s_n_v)<br />
{<br />
	int next_v,min,v_count=1;<br />
	long path_length=0;<br />
	min_circuit[0]=s_v;<br />
	min_circuit[1]=s_n_v;<br />
	set_visited(s_n_v,TRUE);<br />
	path_length+=matrix[s_v][s_n_v];<br />
	for(int V=s_n_v;v_count<n-1;v_count++)<br />
	{       	min=INFI;<br />
			for(int i=0;i<n;i++)<br />
				if(	matrix[V][i]<INFI && !visited[i]<br />
					&& matrix[V][i]<=min<br />
				  )<br />
					min=matrix[V][next_v=i];<br />
		set_visited(next_v,TRUE);<br />
		V=min_circuit[v_count+1]=next_v;<br />
		path_length+=min;<br />
	}<br />
	path_length+=matrix[min_circuit[n-1]][s_v];<br />
	return(path_length);<br />
}<br />
<br />
int main()<br />
{<br />
	//printf("Make sure that infinity value < sum of all path distances\nSet Infinity at (signed long):");<br />
	//scanf("%ld",&INFI);<br />
	INFI=(1<<28)-1;<br />
<br />
	int pathcount,i,j,source,dest,nxt;<br />
	long dist=0;<br />
	long new_circuit_length=INFI;<br />
	printf("Enter no. of cities(MAX:%d):",MAXCITIES);<br />
	scanf("%d",&n);<br />
	if (n > MAXCITIES){<br />
		printf("ERROR: Number of cities is more than max of %d\n", MAXCITIES);<br />
		return -1;<br />
	}<br />
<br />
	printf("Enter paths:< source_id destination_id distance >\n ids varying from 0 to %d\n",n-1);<br />
	//init all matrix distances to infinity<br />
	for(i=0;i<n;i++)<br />
		for(j=0;j<n;j++)<br />
			matrix[i][j]=INFI;<br />
<br />
	//Read in distance values for all possible paths in matrix (except from a node to itself).<br />
	for (i=0;i<n;i++){<br />
		for(j=0;j<n;j++){<br />
			scanf("%d",&nxt);<br />
			if (i != j){ matrix[i][j]=nxt; }<br />
		}<br />
	}<br />
<br />
/*******<br />
	//printf("Enter path count:");<br />
	//scanf("%d",&pathcount);<br />
<br />
	//populate the matrix<br />
	for(i=0;i<pathcount;i++)<br />
	{<br />
		printf("[path %d]:",i);<br />
		scanf("%d %d %ld",&source,&dest,&dist);<br />
		if(source!=dest)<br />
		     matrix[source][dest]=matrix[dest][source]=dist;<br />
	}<br />
*******/<br />
<br />
	visited=new long[n];<br />
	min_circuit=new long[n];<br />
	ham_circuit=new long[n+2];<br />
	min_circuit_length=INFI;<br />
	// algorithm<br />
	//for each vertex, S_V as a staring node<br />
	for(int S_V_id=0;S_V_id<n;S_V_id++)<br />
	{<br />
		printf("."); fflush(stdout);<br />
	        //for each and non start vertex as i<br />
		for(i=0;i<n;i++)<br />
		{       //set all to unvisited<br />
			set_visited(ALL,FALSE);<br />
			// set staring vertex as visited<br />
			set_visited(S_V_id,TRUE);<br />
			//reset/init minimum circuit<br />
			reset_min_circuit(S_V_id);<br />
			// obtain circuit for combination of S_V and i<br />
			new_circuit_length=get_valid_circuit(S_V_id,i);<br />
			// if newer length is less than the previously<br />
			//calculated min then set it as min and set the<br />
			//current circuit in hamiltonion circuit<br />
			if(new_circuit_length<=min_circuit_length)<br />
				SET_HAM_CKT(min_circuit_length=new_circuit_length);<br />
		}<br />
	}<br />
	printf("\n");<br />
// if any circuit found<br />
if(min_circuit_length<INFI)<br />
{<br />
	printf("\n\nMinimum circuit length is: %ld\nCircuit is:\n",min_circuit_length);<br />
	for(i=1;i<n+2;i++)	printf("<%ld> ",ham_circuit[i]);<br />
	printf("\n");<br />
}<br />
else	printf("\n\nNo hamiltonian circuit !");<br />
delete []visited;<br />
delete []min_circuit;<br />
delete []ham_circuit;<br />
}<br />