Código de C/Visual C - Algoritmo para la resolución del coste de recorridos mínimos

Algoritmo para la resolución del coste de recorridos mínimosgráfica de visualizaciones


C/Visual C

estrellaestrellaestrellaestrellaestrella(13)
Publicado el 17 de Mayo del 2002 por Patricio Gutiérrez
12.928 visualizaciones desde el 17 de Mayo del 2002. Una media de 21 por semana
Algoritmo para la resolución del problema de mínimos costes entre pares de nodos.

Esta es la solución al Problema del Camino Mínimo en grafos, en una implementación sencilla, con estructura de datos estática fácilmente transformable a estructura dinámica a través de matrices dispersas (spare matrix). El programa lee una matriz de costos de un grafo y devuelve la matriz de costos de caminos mínimos entre pares de nodos, para luego hallar el camino de menor coste.

Versión 1
estrellaestrellaestrellaestrellaestrella(13)

Publicado el 17 de Mayo del 2002gráfica de visualizaciones de la versión: Versión 1
12.929 visualizaciones desde el 17 de Mayo del 2002. Una media de 21 por semana
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/* 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)

Naty G.
21 de Mayo del 2002
estrellaestrellaestrellaestrellaestrella
Me salvó de tronar la clase
Responder
Ruben Ruiz Perez
03 de Junio del 2002
estrellaestrellaestrellaestrellaestrella
No corre en Dev-C++ 4 (y tune unos erroscillos)
Responder
Omar Castro
03 de Junio del 2002
estrellaestrellaestrellaestrellaestrella
Tu programa tiene mucho errores y no se puede correr en ningun compilador lamento que sea asi ya que era mi tarea.
Responder
Walter Gómez
18 de Junio del 2002
estrellaestrellaestrellaestrellaestrella
Me parece una magnifica idea de programacion, de hecho me adelanto parte de un trabajo, gracias, Patricio. Perdoname, pero me tome la atribucion de hacerle algunas correcciones sintacticas a tu codigo, ahora si lo pueden compilar que corre. No he analizado si es correcto aun, ni su eficiencia, pero por lo menos no podran decirte mas que no corre :-)

#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();
}
Responder
Patricio
25 de Junio del 2002
estrellaestrellaestrellaestrellaestrella
Es un algoritmo para C estándar o Turbo C, no para C++ y en compiladores para esos lenguajes corre perfecto.
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.
Responder
Rodrigo N.
18 de Septiembre del 2002
estrellaestrellaestrellaestrellaestrella
Bueno no lo pude correr en c++ 5.0 asi es que no te puedo decir que hace todo lo que dices......
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
Responder
Camilo
10 de Abril del 2003
estrellaestrellaestrellaestrellaestrella
Estuve mirando el algoritmo le arrgle lo de los "\" y corre pero ingreso los valored delo nodos y costos .
Pero despues no muetra nada !!!
Que toca hacer ademas de eso para que corra bien???
Responder
yeyo
25 de Noviembre del 2004
estrellaestrellaestrellaestrellaestrella
Ha realizado una valoración positiva de este curso.
Responder
yurisnel
01 de Marzo del 2005
estrellaestrellaestrellaestrellaestrella
bueno y que me dicen de un grafo donde exista mas de un camino de un mismo vertice a otro..
alguien me puede dar una recomendacion de como hacerlo ..
Responder
Sergio Carrion
05 de Mayo del 2005
estrellaestrellaestrellaestrellaestrella
Buena aplicacion para la solucion del Algoritmo de Dijkstra
Responder
Kharlos
16 de Mayo del 2006
estrellaestrellaestrellaestrellaestrella
muy buen codigo, me ayudo mucho a pasar estructuras de datos 2 y de desvelarme jaja, el codigo ke pone patricio al compilarlo en turbo c te marca muchos errore pero no se desanimen walter gomez corrigio algunos errores y ya jalo, cheken el codigo correcto aki abajoç

y muchas gracias a patricio gutierrez y walter gomez
Responder
Kharlos
16 de Mayo del 2006
estrellaestrellaestrellaestrellaestrella
muy buen codigo, me ayudo mucho a pasar estructuras de datos 2 y de desvelarme jaja, el codigo ke pone patricio al compilarlo en turbo c te marca muchos errore pero no se desanimen walter gomez corrigio algunos errores y ya jalo, cheken el codigo correcto aki abajoç

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();
}
Responder
Patricio
07 de Junio del 2008
estrellaestrellaestrellaestrellaestrella
Muy didactico.
Responder

Comentar la versión: Versión 1

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios

http://lwp-l.com/s187