return false;
bool hamiltonianCycle() {
for (int i = 0; i < NODE; i++)
path[i] = -1;
path[0] = 0; //first vertex as 0
if ( cycleFound(1) == false ) {
cout << "Solution does not exist"<<endl;
return false;
displayCycle();
return true;
int main() {
hamiltonianCycle();
Output
Cycle: 0 1 2 4 3 0
23
Traveling Salesman Problem (TSP) Implementation
Travelling Salesman Problem (TSP) : Given a set of cities and distances between every pair of
cities, the problem is to find the shortest possible route that visits every city exactly once and
returns to the starting point.
Note the difference between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is to
find if there exists a tour that visits every city exactly once. Here we know that Hamiltonian Tour
exists (because the graph is complete) and in fact, many such tours exist, the problem is to find a
minimum weight Hamiltonian Cycle.
For example, consider the graph shown in the figure on the right side. A TSP tour in the graph is
1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80.
The problem is a famous NP-hard problem. There is no polynomial-time known solution for this
problem.
Examples:
Output of Given Graph:
minimum weight Hamiltonian Cycle :
10 + 25 + 30 + 15 := 80
Recommended: Please try your approach on {Practice} first, before moving on to the solution.
In this post, the implementation of a simple solution is discussed.
24
1. Consider city 1 as the starting and ending point. Since the route is cyclic, we can consider any
point as a starting point.
2. Generate all (n-1)! permutations of cities.
3. Calculate the cost of every permutation and keep track of the minimum cost permutation.
4. Return the permutation with minimum cost.
Below is the implementation of the above idea
// CPP program to implement traveling salesman
// problem using naive approach.
#include <bits/stdc++.h>
using namespace std;
#define V 4
// implementation of traveling Salesman Problem
int travllingSalesmanProblem(int graph[][V], int s)
// store all vertex apart from source vertex
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
25
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 = s;
for (int i = 0; i < vertex.size(); i++) {
current_pathweight += graph[k][vertex[i]];
k = vertex[i];
current_pathweight += graph[k][s];
// update minimum
26
min_path = min(min_path, current_pathweight);
} while (
next_permutation(vertex.begin(), vertex.end()));
return min_path;
// Driver Code
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 s = 0;
27
cout << travllingSalesmanProblem(graph, s) << endl;
return 0;
Output
80
Time complexity: O(n!) where n is the number of vertices in the graph. This is because the
algorithm uses the next_permutation function which generates all the possible permutations of
the vertex set.
Auxiliary Space: O(n) as we are using a vector to store all the vertices.
C program to find the Euclidean distance between two points
Given four integers x1, y1, x2 and y2, which represents two coordinates (x1, y1) and (x2, y2) of
a two-dimensional graph. The task is to find the Euclidean distance between these two points.
Euclidean distance between two points is the length of a straight line drawn between those two
given points.
Examples:
Input: x1, y1 = (3, 4)
x2, y2 = (7, 7)
Output: 5
Input: x1, y1 = (3, 4)
x2, y2 = (4, 3)
Output: 1.41421
Approach: Since the Euclidean distance is nothing but the straight line distance between two
given points, therefore the distance formula derived from the Pythagorean theorem can be used.
28
