Camino minimio

alexander
31 de Enero del 2006
Hola

Estoy enfrascado en un proyecto relacionado con grafos y ya implemente casi todoas las cosas, pero el proyecto requiere, aparte de dar el camino minimo del grafo, dar varias soluciones de camino minimo.

Si alguno de ustedes tiene alguna idea o conoce de algun algoritmo, por favor responde este mensaje
Puedes escribirme a:
[email protected]
[email protected]

gracias de antemano

alexander




Noel Solw
31 de Enero del 2006
Cual es la estructura de datos para representar la red de caminos ?
La longitud de los tramos del camino es variables o todos los tramos tienen la misma longitud ?

alexander
31 de Enero del 2006
Noel la estructura que estoy utilizando es grafo (ponderado), la longitud de los tramos del camino es variable.

Edgarin
31 de Enero del 2006
Usa el algoritmo de Dijkstra, busca como funciona para que entiendas el siguiente codigo que usé:

//Algoritmo de Dijskstra para el camino mínimo. Hecho por Edgar Villegas
#include<iostream.h>

#define I 10000 //Para el infinito
const N=6; //Numero de vértices

//Matriz de adyacencia ponderada (Infinito si no hay conexion directa)
//(Esta matriz es un ejemplo, aqui debes reemplazar por tu grafo)
float C[N][N]={
{I,3,4,I,8,I},
{I,I,I,I,5,I},
{I,I,I,I,3,I},
{I,I,I,I,I,I},
{I,I,I,7,I,3},
{I,I,I,2,I,I},
};

//T es un vector de N parejas vertice-distancia
//Es el Vector principal (en el se desarrolla todo el algoritmo)
struct
{float dist;
int ult; //Ultimo vertice que produjo dist minima
}T[N];

void mostrarT()
{for(int i=1;i<N;i++)
cout<<"t"<<T[i].dist<<",v"<<T[i].ult;
cout<<endl;
}

//Inicia T con el caso base
void iniciarT()
{for(int i=0;i<N;i++) //Inicia T con la primera fila de C
{T[i].dist=C[0][i];
T[i].ult=0;
}
}

//Halla el nuevo vertice a habilitar
int minimo(int habilitados[N])
{float dmin=I;
int vmin;
for(int i=1;i<N;i++)
if(habilitados[i]==0 && T[i].dist<dmin)
{vmin=i;
dmin=T[i].dist;
}
return vmin;
}

//Funcion principal. Almacena en T todo lo necesario, y lo muestra en cada iteración
void Dijkstra()
{int w; //w sera el vertice de menor distancia
int habilitados[N]={1}; //Ej.- Si habilitados[3]=1, v3 esta habilitado
iniciarT();
for(int i=1;i<=N-1;i++) //N-1 pasos
{
mostrarT();
w=minimo(habilitados);
habilitados[w]=1; //Habilita el vertice de menor distancia
for(int v=1;v<N;v++)
{if(habilitados[v]==0)
if( T[w].dist+C[w][v] < T[v].dist)
{T[v].dist=T[w].dist+C[w][v];
T[v].ult=w;
}
}
}
}

//Muestra el camino minimo entre v0 y vdest
void mostrarCaminoMinimo(int dest)
{int rutaAlReves[N], l=0;
cout<<endl<<"A v"<<dest;
cout<<"tDistancia: "<<T[dest].dist<<"tRuta: v0";
while(dest!=0)
{rutaAlReves[l++]=dest;
dest=T[dest].ult;
}
for(int i=l-1;i>=0;i--) //Mostramos al reves
cout<<",v"<<rutaAlReves[i];
}

void main()
{
Dijkstra();
cout<<endl<<"CAMINOS MINIMOS";
for(int v=1;v<N;v++)
mostrarCaminoMinimo(v);
}