Question

C++ data structure problem. (Thanks)

Traveling Salesman Problem Exercise

Consider 5 cities of interest, namely a) Reno, b) San Francisco, c) Salt Lake City, d) Seattle, and e) Las Vegas. Use information on the road network and derive the miles from one city to the other. Then on that basis, conduct the following:

 Create a graph with each of its vertices correspond to one of these cities and its edges being weighted by the associated weights. Note that if (and only if) to go from city A to B you must go through C then you must add one edge from A to C and one edge from C to B and there is no need to add an edge directly from A to B.

 Solve the Traveling Salesman Problem such that traveling salesman starts from Reno, visits all cities in the above list and returns to list. Solve this problem in the brutal forceway,

i.e. by identifying all possible paths. Submit your solution in terms of a) code, and b) a *.txt all possible paths and the best one selected by the algorithm.

Answer 1

// CPP program to implement traveling salesman
// problem using naive approach.
#include <bits/stdc++.h>
using namespace std;
#define V 5

// implementation of traveling Salesman Problem
float travllingSalesmanProblem(float graph[][V], int s)
{
   // store all vertex apart from source vertex
   vector<int> vertex;
   int path[V],temp[V];
   for (int i = 0; i < V; i++)
       if (i != s)
           vertex.push_back(i);

   // store minimum weight Hamiltonian Cycle.
   float min_path = INT_MAX;
   do {

       // store current Path weight(cost)
       float current_pathweight = 0;
      
       // compute current path weight
       int k = s;
       cout<<k+1<<"->";
       for (int i = 0; i < vertex.size(); i++) {
          
           current_pathweight += graph[k][vertex[i]];
           k = vertex[i];
           temp[i]=k;
       }
       current_pathweight += graph[k][s];
       for(int i = 0; i < V-1; i++)
       {
           if(i==V-2) cout<<temp[i]+1<<endl;
           else cout<<temp[i]+1<<"->";
           //i=i+2;
       }
       // update minimum
       min_path = min(min_path, current_pathweight);
       if(min_path==current_pathweight)
       {
           for(int i = 0; i < V-1; i++)
           {
               path[i]=temp[i];
           }
       }
      
   } while (next_permutation(vertex.begin(), vertex.end()));
   cout<<s+1<<"->";
   for(int i = 0; i < V-1; i++)
   {
       if(i==V-2) cout<<path[i]+1<<"->"<<s+1<<endl;
       else cout<<path[i]+1<<"->";
       //i=i+2;
   }
   return min_path;
}

// driver program to test above function
int main()
{
   // matrix representation of graph

//0-Reno, 1- San Francisco, 2- Salt Lake City, 3- Seattle, 4- Las Vegas
   float graph[][V] = { { 0, 185.33, 426.99, 571.99, 344.60 },
                   { 185.33, 0, 599.30, 678.73, 416.83 },
                   { 426.99, 599.30, 0, 699.85, 362.57 },
                   { 571.99, 678.73, 699.85, 0, 871.36 },
                   {344.60, 416.83, 362.57, 871.36, 0 }
                   };
   int s = 0;
   cout << travllingSalesmanProblem(graph, s) << endl;
   return 0;
}