/* Solución al problema de caminos mínimos */
/* Util para Optimizaci¢n e Investigaci¢n Operativa */
/* Programa implementado por Patricio Gutiérrez Z. */
/* Departamento de Ingeniería Informática */
/* Universidad de Santiago de Chile */
#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();
}
Comentarios sobre la versión: Versión 1 (13)
#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)
{
return a<=b?a:b;
}
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();
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();
}
Es una versión sencilla para una implementación funcional que ayuda bastante para ilustrar el problema sobretodo con fines educativos.
Los errores que salían en el código eran por que antes de algunos caracteres salía un backslash ( "\" ).
Atte. Patricio.
Tan solo lo queria para simular una red LAN utilizando nodos buscando el camino mas corto simulando la velocidad y la distancia de la conexion, pero creo que utilizare Visual Basic porque no soy un experto en c/c++
Gracias de antemano amigo Chileno
Pero despues no muetra nada !!!
Que toca hacer ademas de eso para que corra bien???
alguien me puede dar una recomendacion de como hacerlo ..
y muchas gracias a patricio gutierrez y walter gomez
y muchas gracias a patricio gutierrez y walter gomez
#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)
{
return a<=b?a:b;
}
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();
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();
}