#include <stdio.h>
#include <conio.h>


#define MN 100 /* Número máximo de vertices*/
#define infinito 32767

/*Sea*/
int w[MN][MN],q[MN][MN];
unsigned char i,j;
int N;

int min(int a,int b)
{
int r;
if ( a<=b ) r=a ; else r=b;
return(r);
}

void ceros_grafo(int g[MN][MN])
{ unsigned char i,j;

for (i=1;i< N+1;i++ )
for (j=1; j< N+1;j++ )
g[i][j]=0;
}

void camino_min_a( )
{
unsigned char i,k,j;
int qikqkj;

/*Genera nueva matriz de costos q donde nodos inconexos cuestan infinito*/
ceros_grafo(q);
for (i=1;i< N+1 ;i++)
for (j=1; j< N+1;j++ )
if ( (w[i][j]==0) ) q[i][j] = infinito;
else q[i][j]=w[i][j];
/*Busca los costos m¡nimos*/
for (k=1; k< N+1;k++ )
for (i=1 ;i< N+1;i++ )
for (j=1;j< N+1;j++ )
if ( (q[i][k] != infinito) && (q[k][j] != infinito)
) q[i][j] = min(q[i][j],q[i][k] + q[k][j]);

};

void camino_min_sc(int w[MN][MN], int q[MN][MN] )
{ unsigned char i,k,j;
int qikqkj;

/*Genera nueva matriz de costos q donde nodos inconexos cuestan infinito*/
ceros_grafo(q);
for (i=1; i < N+1 ;i++ )
for (j=1; j< N+1;j++ )
if ( (w[i][j]==0) ) q[i][j] = infinito;
else q[i][j]=w[i][j];
/*Busca los costos m¡nimos*/
for (k=1; k< N+1;k++)
for (i=1; i < N+1;i++ )
for (j=1; j< N+1;j++ )
if ( (i!=j) && ((q[i][k] != infinito) && (q[k][j] != infinito))
) q[i][j] = min(q[i][j],q[i][k] + q[k][j]);
};

void muestra_matriz_grafo(int g[MN][MN])
{
unsigned char i,j,Y;

Y = wherey();
for (i=1; i< N+1;i++ )
for (j=1;j < N+1;j++ ) {
gotoxy(5 + j * 6, Y + i);
if ( (g[i][j] != infinito) ) printf(\"%i\",g[i][j])
; else printf(\"ª\");
};
printf(\"\\n\");
}

/* RUTINA PRINCIPAL */
/* ******************************************** */
void main()
{ clrscr();
N=0;
printf(\"Indique:\\n\");
do {
printf(\"Numero de Nodos [1..7]:\");
scanf(\"%i\",&N);
if ( (N < 0) || (N > MN) ) N=0;
} while ( N==0 );

/* Llenado de Matriz de costos w*/

for (i=1;i<N+1; i++ ) {
printf(\"Desde el nodo %i \\n\", i);
for (j=1; j< N+1;j++)
if ( (i!=j) )
{
printf(\"Costo [ %i ÄÄ> %i ]: \",i,j);
scanf(\"%i\",&w[i][j]);
}
else w[i][j]=0;
printf(\"\\n\");
};

/* Calcula los caminos minimos de w y los deja en q*/
clrscr();
printf(\"Matriz de costos original.\\n\");
muestra_matriz_grafo(w);

printf(\"Matriz de costos mínimos.\\n\");
camino_min_a(w,q);
muestra_matriz_grafo(q);

getchar();
clrscr();
printf(\"Matriz de costos original.\\n\");
muestra_matriz_grafo(w);

printf(\"Caminos mínimos sin ciclos.\\n\");
camino_min_sc(w,q);
muestra_matriz_grafo(q);
getch();
}

= no busque siempre que le hagan programas, espero que esto le sirva :-/

http://www.denunciando.com/signature...ic464660_8.gif

http://i898.photobucket.com/albums/a...-USERBAR-1.gif

http://www.atenas.cult.cu/?q=system/...1746/13556.gif

http://t3.gstatic.com/images?q=tbn:A...Xrlc3byNYyrdd2