|
|||||||
|
|
|
|||||
|
|
|||||||
|
|||||||
|
|
|
|||||
|
|
|||||||
Este probema consiste en que dado un conjunto finito de vertices y arcos, se determine el vertice de menor excentricidad, o en terminos reales el vertice "centro de operaciones" del cual se minimizan los costos de transporte.
Ejemplo :
Se quiere establecer el centro de operaciones para la línea AeroPerú. Los ciudades candidatos son Santiago, Miami y Lima. Después de hacer un estudio de costos se llegó a la siguiente situación :
|
Destinos : |
Una de las técnicas existente, es llevar los costos asociados de cada camino a una matriz, en donde la posición (fila,columna), representa el vertice inicial y final respectivamente.
El arco que representa el camino Miami - Santiago (v1 -> v2) se identifica
en la matriz como :
matriz[0][1] = 8
, ya que
fila = 0 : vertice inicial (V1)
columna = 1 : vertice final (V2)
costo = 8
Como el grafo no es dirigido, o sea los caminos se dan en ambos sentidos, el viaje de Santiago a Miami (v2 -> v1) se representa en la matriz como : matriz[1][0] = 8
Se puede intuir que la matriz de costos es de tipo NxN, donde N : numero de vertices.
Tabla de costos
| --- | 8 | 6 |
| 8 | --- | 2 |
| 6 | 2 | --- |
A partir de esta tabla de costos, se hacen una serie de operaciones matemáticas, con el propósito de encontrar el centro del grafo.
Representación de un arco
Para almacenar la información correspondiente a los arcos, creamos una estructura con los siguientes campos :
vi : vertice inicial del arco --> 0 ... número de vertices - 1
vf : vertice final del arco --> 0 ... número de vertices - 1
c : costo asociado
typedef struct
{
int vi , vf;
int c;
} T_ARCO , *ARCO;
Teniendo la estructura , definimos tres funciones para esta estructura :
1 ) crear arco : reservar memoria dinamica para almacenar una variable de tipo T_ARCO, además de inicializar los campos.
ARCO crear_arco(int vi, int vf, int costo)
{
ARCO aux = NULL;
aux = (ARCO) malloc(sizeof(T_ARCO));
aux->vi = vi;
aux->vf = vf;
aux->c = costo;
return aux;
}
2 ) crear arreglo de arcos : reservar memoria dinámica para crear un arreglo de tamaño num_arcos (numero de arcos) de tipo ARCO. Dado que el tipo ARCO es un puntero, lo que se esta haciendo es crear un arreglo de punteros.
ARCO *crear_arr_arcos(int num_arcos)
{
ARCO *aux = NULL;
aux = (ARCO *) calloc(num_arcos,sizeof(ARCO));
return aux;
}
En un grafo no dirigido, un camino de dos sentidos, se considera como un sólo arco (según esta implementación).
3 ) destruir arcos : liberar memoria para el arreglo de arcos.
void destruir_arcos(ARCO *arr, int num_arcos)
{
for(int i = 0; i < num_arcos; i++) free(arr[i]);
free(arr);
}
Las funciones que acabamos de implementar , nos sirven para leer la información de cada arco, según el siguiente seudo-programa :
int main()
{
:
:
< Leer num_arcos ... >
ARCO *arr_arcos = crear_arr_arcos(num_arcos);
for(int i = 0; i < num_arcos; i++)
{
< Leer vi,vf,costo ... >
arr_arcos[i] = crear_arco(vi,vf,costo);
}
< RESTO DEL PROGRAMA ... >
destruir_arcos(arr_arcos);
:
:
return 0;
}
Matriz de costos
La dimensión o tamaño de la matriz de costos está determinada por el número de vertices del grafo, por lo tanto podemos crear una función que cree un matriz dinámica de tipo int.
int **crear_matriz_costos(int num_vertices)
{
int **aux = NULL;
aux = (int **) calloc(num_vertices,sizeof(int *));
for(int i = 0; i < num_vertices; i++)
aux[i] = (int *) calloc(num_vertices,sizeof(int));
return aux;
}
Ya que implementamos la reserva de memoria, creamos una función que libere memoria.
void destruir_matriz_costos(int **matriz, int num_vertices)
{
for(int i = 0; i < num_vertices; i++) free(matriz[i]);
free(matriz);
}
Ejemplo :
int **matCostos = crear_matriz_costos(5);
:
:
destruir_matriz_costos(matCostos,5);
Algoritmo de Floyd
Este algoritmo se puede describir en los siguientes pasos :
1 ) Inicializar una matriz de costos "infinitos". Esto indica que no existe arco entre vertices o que el costo de ir de un vertice a otro es demasiado alto.
Si se esta trabajando con costos del orden de : 1....30 , una constante adecuada para representar este elevado costo, puede ser 2000. Por lo tanto en el programa se puede definir :
#define NO_EXISTE_ARCO 2000
Para inicializar la matriz con este valor, podemos implementar la siguiente función :
void inic_matriz_costos(int **mat_costos , int num_vertices)
{
for(int i = 0; i < num_vertices; i++)
for(int j = 0; j < num_vertices; j++)
mat_costos[i][j] = NO_EXISTE_ARCO;
}
2 ) Pasar la información del arreglo de arcos, a la matriz. Lo que se quiere es deteminar en que posición de la matriz, va a ir el costo asociado a cada arco. Además, si el grafo es no dirigigo, con la información de un arco, asignamos dos costos, en forma simétrica.
Parametros : int **mat_costos , ARCO *arr, int num_arcos , int dirigido vertice inicial --> fila = arr[i]->vi; vertice final --> columna = arr[i]->vf; costo --> mat_costos[fila][columna] = arr[i]->c; SI (NO dirigido) ENTONCES mat_costos[columna][fila] = arr[i]->c; Función :
void asignar_costos(int **mat_costos, ARCO *arr , int num_arcos, int dirigido)
{
int i,f,c;
for(i = 0; i < num_arcos; i++)
{
f = arr[i]->vi;
c = arr[i]->vf;
mat_costos[f][c] = arr[i]->c;
if (!dirigido) mat_costos[c][f] = arr[i]->c;
}
}
3 ) Evaluar la matriz de costos , en la función floyd( ) que realiza los siguientes pasos :
a) Asigna 0 a la diagonal principal b) Busca la excentricidad de cada vertice c) Determina un arreglo con los mayores valores de cada columna. d) Busca el menor elemento del arreglo e) Retorna la posición de ese elemento
La posición retornada corresponde al vertice con menor excentricidad o centro del grafo.
int floyd(int **matriz, int num_vertices)
{
int i,j,k;
for (i = 0; i < num_vertices; i++) matriz[i][i] = 0;
int suma;
for(k = 0; k < num_vertices; k++)
{
for(i = 0; i < num_vertices; i++)
for(j = 0; j < num_vertices; j++)
{
suma = matriz[i][k] + matriz[k][j];
if ( suma < matriz[i][j] ) matriz[i][j] = suma;
}
}
int *arreglo_aux = (int *) calloc(num_vertices,sizeof(int));
int max_col;
for (i = 0 ; i < num_vertices;i++)
{
max_col = -12000;
for(k = 0 ; k < num_vertices; k++)
if (matriz [i][k] > max_col)
if(matriz[i][k] != NO_EXISTE_ARCO)
max_col = matriz[i][k];
arreglo_aux[i] = max_col;
}
int posicion;
int menor = 20000;
printf("\n \n Arreglo con los maximos ");
for (k = 0; k < num_vertices;k++)
{
printf(" %d ",arreglo_aux[k]);
if (arreglo_aux[k] != 0)
if ( arreglo_aux[k] < menor )
{
menor = arreglo_aux[k];
posicion = k;
}
}
free(arreglo_aux);
return posicion;
}
ALGORITMO DEL PROGRAMA PRINCIPAL
Leer num_arcos, num_vertices Leer dirigido (1 = si / 0 = no) Crear y leer el arreglo de arcos Crear la matriz de costos Inicializar la matriz Asignar costos del arreglo de arcos a la matriz Aplicar floyd Imprimir el vertice resultante Liberar memoria -------------