Problema del agente viajero

[nandaarea]

Hola se supone que tengo que hacer el programa que muestre el costo minimo y la ruta la cual debe de tomar . El programa que hice pide el tamaño de un arreglo que seria las ciudades a las que debe ir el agente, despues es pide los costos del trayecto; el profesor nos puso un ejemplo en el cual me estoy basando para hacer el programa el ejemplo es el siguiente:

tabla de costos:
| 999,10,15,20 |
| 5,999,9,10 |
| 6,13,999,12 |
| 8 ,8,9,999|

Costo minimo 35
Trayecto 1a2, 2a4, 4a3, 3a1

El programa Calcula el costo minimo pero no se como hacer que la funcion tps muestre el trayecto o tendría que crear otra funcion que haga el trayecto la verdad no tengo idea de como hacer que el programa haga eso en eso necesito su ayuda.

El 999 es que noo existe una ruta .

Aqui el codigo:

Código C:

#include <stdio.h>
#include <stdlib.h>
int tsp(int **c, int *g, int ini, int n);
main (){
     int t,i,j,**c,*g,cost;
     printf("ingrese el tamaño del arreglo: ");
     scanf("%d",&t);
     c=(int**)calloc(t+1,sizeof(int*));
     for(i=0;i<t;i++){
         c[i]=(int*)calloc(t+1,sizeof(int));
         }
     for(i=0;i<t;i++){
         for(j=0;j<t;j++){
             printf("ingrese los valores [%d][%d]: ",i+1,j+1);
             scanf("%d",&c[i][j]);
             }        
         }
     g=(int*)calloc(t+1,sizeof(int));
     for(i=0;i<t;i++)
     g[i]=i;
     cost=tsp(c,g,0,t);
     printf("costo minimo: %d",cost);
     getchar();
     getchar();
}
int tsp(int **c, int *g, int ini, int n){
    int i, j, k,*temp,*ming, mincost, ccost;
    if(ini==n-2)
    return c[g[n-2]][g[n-1]]+c[g[n-1]][0];
    mincost=999;  
    temp=(int*)calloc(n+1,sizeof(int));
    for(i=ini+1;i<n;i++){
        for(j=0;j<n;j++)
             temp[j]=g[j];
            temp[ini+1]=g[i];
            temp[i]=g[ini+1];
            if(c[g[ini]][g[i]]+(ccost=tsp(c,temp,ini+1,n))<mincost){
               mincost=c[g[ini]][g[i]]+ccost;
               ming=(int*)calloc(n+1,sizeof(int));
               for(k=0;k<n;k++)
               ming[k]=temp[k];
               }
    }
    return mincost;
}
 

Espero puedan ayudarme