Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // CPP program to implement traveling salesman
- // problem using naive approach.
- //#include <bits/stdc++.h>
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cstdlib>
- #include <climits>
- using namespace std;
- #define V 4
- // implementation of traveling Salesman Problem
- int travllingSalesmanProblem(int graph[][V], int start)
- {
- // store all vertex apart from source vertex
- vector<int> vertex;
- for (int i = 0; i < V; i++)
- if (i != start)
- vertex.push_back(i);
- // store minimum weight Hamiltonian Cycle.
- int min_path = INT_MAX;
- do {
- // store current Path weight(cost)
- int current_pathweight = 0;
- // compute current path weight
- int k = start;
- for (int i = 0; i < vertex.size(); i++) {
- current_pathweight += graph[k][vertex[i]];
- k = vertex[i];
- }
- current_pathweight += graph[k][start];
- // update minimum
- min_path = min(min_path, current_pathweight);
- } while (next_permutation(vertex.begin(), vertex.end())); //rearrange all vertex index from array
- return min_path;
- }
- // driver program to test above function
- int main()
- {
- // matrix representation of graph
- int graph[][V] = { { 0, 10, 15, 20 },
- { 10, 0, 35, 25 },
- { 15, 35, 0, 30 },
- { 20, 25, 30, 0 } };
- int start = 0;
- cout << travllingSalesmanProblem(graph, start) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement