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
using System ; using System . Collections . Generic ; class TSPGreedy { static void findMinRoute ( int [ , ] tsp ) { int sum = 0 ; int counter = 0 ; int j = 0 , i = 0 ; int min = int . MaxValue ; List < int > visitedRouteList = new List < int > ( ) ; visitedRouteList . Add ( 0 ) ; int [ ] route = new int [ tsp . Length ] ; while ( i < tsp . GetLength ( 0 ) && j < tsp . GetLength ( 1 ) ) { if ( counter >= tsp . GetLength ( 0 ) - 1 ) { break ; } if ( j != i && ! ( visitedRouteList . Contains ( j ) ) ) { if ( tsp [ i , j ] < min ) { min = tsp [ i , j ] ; route [ counter ] = j + 1 ; } } j ++ ; if ( j == tsp . GetLength ( 0 ) ) { sum += min ; min = int . MaxValue ; visitedRouteList . Add ( route [ counter ] - 1 ) ; j = 0 ; i = route [ counter ] - 1 ; counter ++ ; } } i = route [ counter - 1 ] - 1 ; for ( j = 0 ; j < tsp . GetLength ( 0 ) ; j ++ ) { if ( ( i != j ) && tsp [ i , j ] < min ) { min = tsp [ i , j ] ; route [ counter ] = j + 1 ; } } sum += min ; Console . Write ( " Minimum ▁ Cost ▁ is ▁ : ▁ " ) ; Console . WriteLine ( sum ) ; } public static void Main ( String [ ] args ) { int [ , ] tsp = { { - 1 , 10 , 15 , 20 } , { 10 , - 1 , 35 , 25 } , { 15 , 35 , - 1 , 30 } , { 20 , 25 , 30 , - 1 } } ; findMinRoute ( tsp ) ; } }