Travelling Salesman Problem | Greedy Approach | C ++ program for the above approach ; Function to find the minimum cost path for all the paths ; Starting from the 0 th indexed city i . e . , the first city ; Traverse the adjacency matrix tsp [ ] [ ] ; Corner of the Matrix ; If this path is unvisited then and if the cost is less then update the cost ; Check all paths from the ith indexed city ; Update the ending city in array from city which was last visited ; Started from the node where we finished as well . ; Driver Code ; Input Matrix ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findMinRoute ( vector < vector < int > > tsp ) { int sum = 0 ; int counter = 0 ; int j = 0 , i = 0 ; int min = INT_MAX ; map < int , int > visitedRouteList ; visitedRouteList [ 0 ] = 1 ; int route [ tsp . size ( ) ] ; while ( i < tsp . size ( ) && j < tsp [ i ] . size ( ) ) { if ( counter >= tsp [ i ] . size ( ) - 1 ) { break ; } if ( j != i && ( visitedRouteList [ j ] == 0 ) ) { if ( tsp [ i ] [ j ] < min ) { min = tsp [ i ] [ j ] ; route [ counter ] = j + 1 ; } } j ++ ; if ( j == tsp [ i ] . size ( ) ) { sum += min ; min = INT_MAX ; visitedRouteList [ route [ counter ] - 1 ] = 1 ; j = 0 ; i = route [ counter ] - 1 ; counter ++ ; } } i = route [ counter - 1 ] - 1 ; for ( j = 0 ; j < tsp . size ( ) ; j ++ ) { if ( ( i != j ) && tsp [ i ] [ j ] < min ) { min = tsp [ i ] [ j ] ; route [ counter ] = j + 1 ; } } sum += min ; cout << ( " Minimum ▁ Cost ▁ is ▁ : ▁ " ) ; cout << ( sum ) ; } int main ( ) { vector < vector < int > > tsp = { { -1 , 10 , 15 , 20 } , { 10 , -1 , 35 , 25 } , { 15 , 35 , -1 , 30 } , { 20 , 25 , 30 , -1 } } ; findMinRoute ( tsp ) ; }