I$\text{'}$m trying to find a solution to a complete undirectected graph. My idea is to run nearest neighbor on it then use a chepest link clustering algortihm to improve that path. here is my code. However my cheapest link algorithm do$0$

$10$

$230$

This describes a graph with three nodes.

am $=$

$[-12]$

$[1-3]$

$[23-]$clude

#include

#include

#include

using namespace std;

const int INF $=$ INT$\_$MAX;

$//$ Function to find the minimum value and corresponding indices in a matrix

void findMinValue$($const vector$>$& matrix, int& minValue, int& minRow, int& minCol$)\{$

minValue $=$ INF;

for $($int i $=0$; i $<$ matrix.size$()$; $++$i$)\{$

for $($int j $=0$; j $<$ matrix$[$i$].$size$()$; $++$j$)\{$

if $($j $!=$ minCol && matrix$[$i$][$j$]<$ minValue$)\{$

minValue $=$ matrix$[$i$][$j$]$;

minRow $=$ i;

minCol $=$ j;

$\}$

$\}$

$\}$

$\}$

$//$ Function to apply Cheapest Link Algorithm on a graph

void cheapestLink$($vector$>$& graph$)\{$

int n $=$ graph.size$()$;

$//$ Initialize clusters with individual vertices

vector$>$ clusters;

for $($int i $=0$; i $<$ n; $++$i$)\{$

clusters.push$\_$back$(\{$i$\})$;

$\}$

int totalDistance $=0$;

vector nodesVisited;

while $($clusters$.$size$()>1)\{$

int minValue $=$ INF;

int minRow $=-1,$ minCol $=-1$;

$//$ Find the minimum value in the graph

findMinValue$($graph$,$ minValue, minRow, minCol$)$;

$//$ Add a check for valid minRow and minCol

if $($minRow $==-1||$ minCol $==-1)\{$

cout $<<"$No valid minimum value found. Exiting." $<<$ endl;

break;

$\}$

$//$ Merge clusters minRow and minCol

vector mergedCluster;

mergedCluster.reserve$($clusters$[$minRow$].$size$()+$ clusters$[$minCol$].$size$())$;

mergedCluster.insert$($mergedCluster$.$end$(),$ clusters$[$minRow$].$begin$(),$ clusters$[$minRow$].$end$())$;

mergedCluster.insert$($mergedCluster$.$end$(),$ clusters$[$minCol$].$begin$(),$ clusters$[$minCol$].$end$())$;

$//$ Update the overall distance

totalDistance $+=$ graph$[$minRow$][$minCol$]$

$//$ Update nodesVisited

nodesVisited.insert$($nodesVisited$.$end$(),$ clusters$[$minRow$].$begin$(),$ clusters$[$minRow$].$end$())$;

nodesVisited.insert$($nodesVisited$.$end$(),$ clusters$[$minCol$].$begin$(),$ clusters$[$minCol$].$end$())$;

$//$ Create a new graph to store the updated distances

vector$>$ updatedGraph$($n $-1,$ vector$($n $-1,$ INF$))$;

$//$ Update the new graph with merged clusters

for $($int i $=0,$ newI $=0$; i $<$ n; $++$i$)\{$

if $($i $!=$ minRow && i $!=$ minCol$)\{$

for $($int j $=0,$ newJ $=0$; j $<$ n; $++$j$)\{$

if $($j $!=$ minRow && j $!=$ minCol$)\{$

updatedGraph$[$newI$][$newJ$]=$ graph$[$i$][$j$]$;

$++$newJ;

$\}$

$\}$

$++$newI;

$\}$

$\}$

$//$ Add the distances from the merged cluster to other clusters in the new graph

for $($int i $=0$; i $<$ n $-2$; $++$i$)\{$

int minG $=$ min$($graph$[$minRow$][$clusters$[$i$][0]],$ graph$[$minCol$][$clusters$[$i$][0]])$;

updatedGraph$[$i$][$n $-2]=$ minG;

updatedGraph$[$n $-2][$i$]=$ minG;

$\}$

$//$ Add a new row and column for the merged cluster in the new graph

updatedGraph$[$n $-2][$n $-2]=0$;

$//$ Update clusters with the merged clusters

clusters.push$\_$back$($mergedCluster$)$;

$//$ Update the graph to the new graph

graph $=$ move$($updatedGraph$)$;

$\}$

$//$ Print the order of nodes traversed

cout $<<$ "Order of nodes traversed: $"$;

for $($int node : nodesVisited$)\{$

cout $<<$ node $<<""$;

$\}$

cout $<<$ endl;

$//$ Print the overall distance traveled

cout $<<$ "Overall distance traveled: $"<<$ totalDistance $<<$ endl;

$\}$

$//$ Function to apply Nearest Neighbor Algorithm on a graph

void nearestNeighbor$($const vector$>$& graph, int startVertex$)\{$

int n $=$ graph.size$()$;

vector visited$($n$,$ false$)$;

vector tour;

tour.push$\_$back$($startVertex$)$;

visited$[$startVertex$]=$ true;

for $($int i $=1$; i $<$ n; $++$i$)\{$

int currentVertex $=$ tour.back$()$;

int nextVertex $=-1$;

int minDistance $=$ INF;

for $($int j $=0$; j $<$ n; $++$j$)\{$

if $(!$visited$[$j$]$ && graph$[$currentVertex$][$j$]<$ minDistance$)\{$

minDistance $=$ graph$[$currentVertex$][$j$]$;

nextVertex $=$ j;

$\}$

$\}$

if $($nextVertex $!=-1)\{$

tour.push$\_$back$($nextVertex$)$;

visited$[$nextVertex$]=$ true;

$\}$

$\}$

$//$ Print the tour obtained from Nearest Neighbor Algorithm

cout $<<$ "Tour obtained from Nearest Neighbor Algorithm starting from vertex $"<<$ startVertex $<<"$:

$"$;

for $($int vertex : tour$)\{$

cout $<<$ vertex $<<""$;

$\}$

cout $<<"$

$"$;

$\}$

int main$()\{$

$//$ Open the file containing the graph

ifstream inputFile$("/")$;

if $(!$inputFile.is$\_$op