Advertisement
KDOXG

Traveling Salesman Problem

Sep 30th, 2019
463
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1.  
  2. // CPP program to implement traveling salesman
  3. // problem using naive approach.
  4. //#include <bits/stdc++.h>
  5. #include <iostream>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <cstdlib>
  9. #include <climits>
  10. using namespace std;
  11. #define V 4
  12.  
  13. // implementation of traveling Salesman Problem
  14. int travllingSalesmanProblem(int graph[][V], int start)
  15. {
  16.     // store all vertex apart from source vertex
  17.     vector<int> vertex;
  18.     for (int i = 0; i < V; i++)
  19.         if (i != start)
  20.             vertex.push_back(i);
  21.  
  22.     // store minimum weight Hamiltonian Cycle.
  23.     int min_path = INT_MAX;
  24.     do {
  25.  
  26.         // store current Path weight(cost)
  27.         int current_pathweight = 0;
  28.          
  29.         // compute current path weight
  30.         int k = start;
  31.         for (int i = 0; i < vertex.size(); i++) {
  32.             current_pathweight += graph[k][vertex[i]];
  33.             k = vertex[i];
  34.         }
  35.         current_pathweight += graph[k][start];
  36.  
  37.         // update minimum
  38.         min_path = min(min_path, current_pathweight);
  39.          
  40.     } while (next_permutation(vertex.begin(), vertex.end())); //rearrange all vertex index from array
  41.  
  42.     return min_path;
  43. }
  44.  
  45. // driver program to test above function
  46. int main()
  47. {
  48.     // matrix representation of graph
  49.     int graph[][V] = { { 0, 10, 15, 20 },
  50.                        { 10, 0, 35, 25 },
  51.                        { 15, 35, 0, 30 },
  52.                        { 20, 25, 30, 0 } };
  53.     int start = 0;
  54.     cout << travllingSalesmanProblem(graph, start) << endl;
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement