Travelling salesman problem java code

Travelling salesman problem

Problem:    Given a complete undirected graph G=(V, E) that has nonnegative integer cost  c(u, v) associated with each edge (u, v) in E, the problem is to find a hamiltonian cycle (tour) of G with minimum cost.

                                                
A salespersons starts from the city 1 and has to visit six cities (1 through 6) and must come back to the starting city i.e., 1. The first route (left side) 1→ 4 → 2 → 5 → 6 → 3 → 1 with the total length of 62 km, is a relevant selection but is not the best solution. The second route (right side) 1 → 2→ 5 → 4 → 6 → 3 → 1 represents the must better solution as the total distance, 48 km, is less than for the first route.

Here is the java code along with output given. Enjoy,

import java.util.Scanner; 

class TSP

 {
    static int c[][],n;

 static int INF=100000; 

 static int cost; 

 static int path[];
    static boolean intour[];

 public static void main(String args[]) 

 {
        int i,j,k; 

 Scanner scr = new Scanner(System.in); 

 System.out.println("Enter no. of vertices"); 

 n = scr.nextInt(); 

 c = new int[n+1][n+1]; 

 path = new int[n+1]; 

 boolean s[] = new boolean[n+1]; 

 intour = new boolean[n+1]; 

 for(i=1;i<=n;i++)

 for(j=1;j<=n;j++) 

{

s[j] = true; 

 if(i==j) 

 {
                    c[i][j]=0; 

 continue; 

 } 

 System.out.println("Is there an edge from vertex "+i+" to vertex "+j+" ?");

 System.out.println("Enter -1 if not else enter corresponding weight"); 

 c[i][j] = scr.nextInt(); 

 if(c[i][j]==-1) 

 c[i][j] = INF; 

 } 

 s[1]=false; 

cost = travellingCost(1,s); 

 System.out.println("Solution :"); 

 System.out.println("Path: "); 

 path[0] = 1; 

 j=0; 

 for(i = 0;i<n;i++) 

 { 

 System.out.print(path[j]+"  "); 

    j = path[j];

 } 

 System.out.print("1"); 

 System.out.println(); 

 System.out.println("Cost: "+cost); 

 } 

 public static boolean allFalse(boolean a[])

 { 

 for(int i = 1;i<=n;i++) 

 if(a[i]) 

 return false; 

return true;

 } 

 public static int travellingCost(int strt,boolean set[]) 

 {
        set[strt] = false; 

 if(allFalse(set)) 

 return c[strt][1]; 

 int minv=0,mincost=INF,p=0,i; 

 for(i = 1;i<=n;i++)

 {
            if(set[i]) 

 {
                boolean t[] = new boolean[n+1]; 

 System.arraycopy(set,1,t,1,n); 

 t[i] = false; 

 p = c[strt][i] + travellingCost(i,t); 

 if(p < mincost)

 {
                      mincost = p;
                      minv = i;
                  } 

 }

 } 

 if(!intour[strt])

 {
          path[strt] = minv; 

 intour[strt] = true; 

 } 

 return mincost; 

 } 

} 

/**
Sample Output: 

Enter no. of vertices
4 

Is there an edge from vertex 1 to vertex 2 ? 

Enter -1 if not else enter corresponding weight
10 

Is there an edge from vertex 1 to vertex 3 ? 

Enter -1 if not else enter corresponding weight
15 

Is there an edge from vertex 1 to vertex 4 ? 

Enter -1 if not else enter corresponding weight
20 

Is there an edge from vertex 2 to vertex 1 ? 

Enter -1 if not else enter corresponding weight
5 

Is there an edge from vertex 2 to vertex 3 ? 

Enter -1 if not else enter corresponding weight
9 

Is there an edge from vertex 2 to vertex 4 ?

 Enter -1 if not else enter corresponding weight
10 

Is there an edge from vertex 3 to vertex 1 ?

 Enter -1 if not else enter corresponding weight
6 

Is there an edge from vertex 3 to vertex 2 ? 

Enter -1 if not else enter corresponding weight
13 

Is there an edge from vertex 3 to vertex 4 ? 

Enter -1 if not else enter corresponding weight
12 

Is there an edge from vertex 4 to vertex 1 ? 

Enter -1 if not else enter corresponding weight
8 

Is there an edge from vertex 4 to vertex 2 ? 

Enter -1 if not else enter corresponding weight
8 

Is there an edge from vertex 4 to vertex 3 ? 

Enter -1 if not else enter corresponding weight
9 

Solution :
Path: 
1  2  4  3  1
Cost: 35 

#################################################