Enrique
Master
Registrado: 13 Ago 2002Mensajes: 261Ubicación: La Vila Joiosa (Alacant)
|
 Publicado: Lun 25 Nov, 2002 4:06 am Asunto: |
 |
|
Hola, ahí va una ayudita (aunque a menudo soy retorcido escribiendo código está bastante documentado):
| Código: | bool Dijkstra(int VerticeInicial, TListaBasadaEnVerticesAlpha *LBValpha,
TListaBasadaEnVerticesBeta *LBVbeta, double *Distancia, int *Predecesor)
{
int fijados = -2; //Para saber si es "conexo" o no
bool *Fijado;
Fijado = new bool[Grafo.V()];
double *M;
M = new double[Grafo.V()];
double *DistanciasNoFijadas;
DistanciasNoFijadas = new double[Grafo.V()];
//PASO 1: Inicialización
for (int i = 0; i < Grafo.V(); i++)
{
Distancia[i] = MAXDOUBLE; //Aquí no existe el concepto infinito,
M[i] = MAXDOUBLE; //lo más parecido está en values.h
Predecesor[i] = i;
Fijado[i] = false;
}
Distancia[VerticeInicial] = 0;
Fijado[VerticeInicial] = true;
//PASO 2
int u = VerticeInicial;
int v;
//PASO 5 (hay Grafo.V() vértices, los estudiaremos todos)
for (int i = 1; i < Grafo.V(); i++)
{
Application->ProcessMessages();
if (Abortar)
goto finDijkstra;
//PASO 3 (búsqueda de nuevos caminos, sólo en los sucesores de u)
for (int j = LBValpha[u].alpha; j < LBValpha[u + 1].alpha; j++)
{
v = IndiceListas(LBVbeta[j].beta, LBValpha);
if (!Fijado[v])
M[v] = Distancia[v] < Distancia[u] + Eje[LBVbeta[j].Eje].Peso ? Distancia[v] :
Distancia[u] + Eje[LBVbeta[j].Eje].Peso;
}
//PASO 3 (actualización de Distancia[] y Predecesor[])
for (int j = 0; j < Grafo.V(); j++)
{
if (!Fijado[j])
{
if (M[j] < Distancia[j])
{
Distancia[j] = M[j];
Predecesor[j] = u;
}
}
}
//PASO 4 (selección del vértice más cercano entre los no fijados)
for (int j = 0; j < Grafo.V(); j++)
{
if (!Fijado[j])
DistanciasNoFijadas[j] = Distancia[j];
else
DistanciasNoFijadas[j] = MAXDOUBLE;
}
u = MinIndice(DistanciasNoFijadas, Grafo.V());
Fijado[u] = true;
}
for (int i = 0; i < Grafo.V(); i++)
if (!Fijado[i])
break;
else
fijados = i;
finDijkstra:
delete[] DistanciasNoFijadas;
delete[] Fijado;
delete[] M;
return (fijados == Grafo.V() - 1);
}
//-----------------------------------------------------------------------------------------
|
Puedes imaginar que TListaBasadaEnVertices, TGrafo, ... son estructuras que tengo definidas y recogen los elementos fundamentales de un grafo.
Si quieres alguna descripción teórica puedes mirar en http://perso.wanadoo.es/fabianx1/tdg.html
Suerte. |
|
FAQ
Buscar
Miembros
Grupos de Usuarios
Registrarse
Perfil
Entra para ver tus mensajes privados
Entrar
