TSP Traveling Salesman Problem O(n!) complexitate

tsp.cpp

/*
Input:
Numar de noduri si matricea costurilor
5
0 9 0 8 0
7 0 1 0 3
5 0 0 0 4
0 0 6 0 0
0 1 0 7 0
*/
#include <iostream>
#include <climits>
#define FIN "tsp.in"
#define FOUT "tsp.out"

using namespace std;

const int SIZE = 100;

int path[ SIZE ];

int matrixCosts[ SIZE ][ SIZE ];

int bestPath[ SIZE ];

bool used[ SIZE ];

int nodes, start_node, bestCost = INT_MAX, currentCost;

void printSol() {

         cout<<"Costul minim: "<<bestCost<<"\n";

         cout<<"Drumul minim: ";

         for(int i = 1; i <= nodes; ++i) {

         	 cout<<bestPath[i]<<" ";
         }

         cout<<start_node;
}

void saveSol() {

	  for(int i = 1; i <= nodes; ++i) {

	  	   bestPath[i] = path[ i ];
	  }
}

void hamilton(int k) {

	 if( k == nodes + 1 ) {
         
	 	 //check for cycle
	 	 if(matrixCosts[path[nodes]][start_node] > 0) {

	 	     int totalCost = currentCost + matrixCosts[ path[nodes] ][ start_node ];

	 	     if(totalCost < bestCost) {

	 	     	   bestCost = totalCost;

	 	     	   saveSol();
	 	     }
	 	 }

	 } else {

	 	  // 4
	 	  // 1
           //daca nodul nu este folosit
             
           for(int v = 1; v <= nodes; ++v) { 

               if(!used[ v ] && matrixCosts[ path[k - 1] ][ v ] > 0)  {
                    
                    int newCost = currentCost + matrixCosts[path[k-1] ][ v ];

                    //branch and bound 
                    if( newCost >= bestCost ) continue;

                    path[ k ] = v;

                    currentCost = newCost;

                    used[ v ] = true;                    
                    
                    hamilton(k + 1);

                    currentCost = currentCost -matrixCosts[ path[k-1] ][ v ];

                    used[ v ] = false;

               }
           }          
	 }

}

int main(int argc, char const *argv[])
{
	
	freopen(FIN, "r", stdin);

	cin>>nodes;

	for(int i = 1; i <= nodes; ++i) {

		for(int j = 1; j <= nodes; ++j) {

			cin>>matrixCosts[i][j];
		}	
	}

    //matricea costurilor
	for(int i = 1; i <= nodes; ++i) {

		for(int j = 1; j <= nodes; ++j) {

			cout<<matrixCosts[i][j]<<" ";
		}	

		cout<<endl;
	}


    //nodul de start
	start_node = 1;

	path[ start_node ] = 1;

    //path[5]
    //path[4]
    //path[3]
    //path[2] = 
	//path[1] = 1

    //marcam nodul de start ca fiind explorat
	used[ start_node ] = true;

    //apelam functia hamilton cu nodul urmator 2
	hamilton( 2 );

    //afisam solutia
    printSol();

	return 0;
}

//Complexitate O(n!)

//gasirea unui ciclu hamiltonian de const minim