RE:Algoritmo de Dijkstra
Publicado por
Juan (1 intervención) el 19/01/2010 14:56:21
GrafoTDA Dijkstra ( GrafoTDA G , int v) {
// Calcula los costos m´ınimos de los caminos desde el
v´ertice v al resto de los v´ertices de I.
// Paso 1
// Conjunto de V´ertices ya visitados
ConjuntoTDA Visitados = {v};
// Paso 2
// Grafo auxiliar
GrafoTDA A;
// Grafo en donde se guarda resultado
GrafoTDA R;
Para cada v´ertice w en Vertices (G) {
Agregar w a los v´ertices de A
Agregar w a los v´ertices de R
}
Para cada v´ertice v´ en Adyacentes_G (v) {
Agregar (v,v´ , Peso_G (v ,v´)) a las aristas de A
Agregar (v,v´ , Peso_G (v ,v´)) a las aristas de R
}
// Conjunto de V´ertices pendientes de calculo
ConjuntoTDA Pendientes = Vertices (G) - Visitados ;
ConjuntoTDA AuxPendientes ;
// Paso 3
whi le ( Pendientes != ConjVac´ıo ) {
elegir un v´ertice w en Pendientes tal que Peso_A (v ,w)
sea m´ınimo ;
// Agrega v´ertice w a Visitados
Visitados = Visitados U {w};
// Saca w de Pendientes
Pendientes = Pendientes - {w };
Copiar Pendientes en Aux_Pendientes ;
whi le ( Aux_Pendientes != ConjVacio ) {
elegir un v´ertice p cualquiera de Aux_Pendientes ;
i f ( Existe arista_A (v,w) y Existe arista_G (w ,p)) {
i f ( Existe arista_A (v,p)) {
i f ( Peso_A (v,w) + Peso_G (w ,p) < Peso_A (v ,p)
){
Agregar [v , p , Peso_A (v,w) + Peso_G (w,p)]
a las aristas de A;
Eliminar Aristas entrantes a p en R;
Agregar [w,p , Peso_G (w ,p)] en R;
}
}
e l s e {
Agregar [v, p , Peso_A (v,w) + Peso_G (w,p)] a
aristas de A;
Agregar [w,p , Peso_G (w,p)] en R;
}
// Saca p de Aux_Pendientes
Aux_Pendientes = Aux_Pendientes - {p};
}
}
return R;
}
