Algoritmo de prim y dijkstra
C/Visual C
Publicado el 19 de Diciembre del 2010 por Marcelo Tabango
31.765 visualizaciones desde el 19 de Diciembre del 2010
Este programa trabaja con memoria dinámica diferentes grafos implementando el algoritmo de prim y dijkstra.
Implementa dijkstra y prim usando punteros, direcciones de memoria.
Muestra el árbol de caminos de la ruta mas corta de un nodo a otro y la suma de los costos mínimos.
Estructuras de datos, grafos, vértices.
Desarrollado en Dev C++ 4.9.9.2
Implementa dijkstra y prim usando punteros, direcciones de memoria.
Muestra el árbol de caminos de la ruta mas corta de un nodo a otro y la suma de los costos mínimos.
Estructuras de datos, grafos, vértices.
Desarrollado en Dev C++ 4.9.9.2
Comentarios sobre la versión: Versión 1 (10)
void desmarcar(){
struct Vertice *ciudad = primeroGrafo;
cantidadDeLineasEje+=2;
asignaciones++;
while( ciudad != NULL ){
ciudad->visitado = false;
ciudad->etiquetaA = 999999;
ciudad = ciudad->sigV;
comparaciones++;
asignaciones+=3;
cantidadDeLineasEje+=4;
}
cout <<"\t Cantidad de lineas Ejecutadas: " << cantidadDeLineasEje << endl;
cout <<"\t Cantidad de Comparaciones: " << comparaciones << endl;
cout <<"\t Cantidad de Asignaciones: " << asignaciones << endl;
cantidadDeLineasEje = 0;
comparaciones = 0;
asignaciones = 0;
primeroPila = NULL;
}
void llamarDijkstra(){
int tipoBusqueda;
cout << "\nSeleccione la ciudad origen\n";
struct Vertice *ciudadOrigen = getCiudadGrafo();
cout << "\nSeleccione la ciudad destino\n";
struct Vertice *ciudadDestino = getCiudadGrafo();
cout << "\nDigite 1 si desea buscar por distancia o 2 por costo: ";
cin >> tipoBusqueda;
cantidadDeLineasEje+=3;
asignaciones+=2;
if( ciudadOrigen != NULL and ciudadDestino != NULL and tipoBusqueda == 1 or tipoBusqueda == 2){
ciudadOrigen->visitado = true;
ciudadOrigen->etiquetaA = 0;
strcpy(ciudadOrigen->etiquetaB, ciudadOrigen->ciudad);
cout << endl << "\n\tEtapa " << etapa << ":" << endl;
cantidadDeLineasEje+=4;
asignaciones+=3;
comparaciones+=4;
etiquetaDijkstraDistancia(ciudadOrigen, ciudadDestino->ciudad, tipoBusqueda);
}
else{
cout << "\n\nEl numero no es valido, intente de nuevo.";
}
}
struct Pila *pop(){
cantidadDeLineasEje++;
asignaciones++;
if( primeroPila == NULL ){
return NULL;
cantidadDeLineasEje+=2;
comparaciones++;
}
else{
struct Pila *pop = primeroPila;
primeroPila = primeroPila->sig;
return pop;
cantidadDeLineasEje+=3;
asignaciones+=2;
}
};
void push(struct Vertice *ciudad){
struct Pila *pila1 = new Pila(ciudad->ciudad, ciudad->etiquetaA);
struct Pila2 *pila2 = new Pila2(ciudad->ciudad);
pila2->sig = pila;
pila = pila2;
pila1->sig = primeroPila;
primeroPila = pila1;
cantidadDeLineasEje+=3;
asignaciones+=3;
}
void mostrarCaminoCorto(){
cantidadDeLineasEje++;
while(primeroPila != NULL ){
struct Pila *pila = pop();
cout << endl << pila->ciudad << "\tPeso: " << pila->peso << endl;
//etapa++;
cantidadDeLineasEje+=3;
asignaciones++;
comparaciones++;
}
desmarcar();
asignaciones++;
cantidadDeLineasEje+=2;
}
void guardarCaminoCorto(struct Vertice *ciudad){
struct Vertice *tempCiudad = ciudad;
cantidadDeLineasEje+=2;
asignaciones++;
while( tempCiudad != NULL ){
push(tempCiudad);
cantidadDeLineasEje+=2;
comparaciones++;
if(strcmp(tempCiudad->ciudad, tempCiudad->etiquetaB) == 0){
cantidadDeLineasEje++;
asignaciones++;
comparaciones++;
break;
}
tempCiudad = getCiudadGrafoAux(tempCiudad->etiquetaB);
cantidadDeLineasEje++;
asignaciones++;
}
mostrarCaminoCorto();
cantidadDeLineasEje++;
}
void escogerMenorEtiquetadoDijkstraDistancia(char *destino, int tipoBusqueda){
int menorDistancia = 999999;
struct Vertice *caminoCorto;
struct Vertice *tempCiudad = primeroGrafo;
cantidadDeLineasEje+=4;
asignaciones+=2;
while( tempCiudad != NULL ){
cantidadDeLineasEje++;
cout << "\n\t\t"<< tempCiudad->ciudad << "\tPeso: " << tempCiudad->etiquetaA;
if(tempCiudad->visitado and tempCiudad->etiquetaA == 0)
cout << "\t\tVisitado\n";
else if(tempCiudad->visitado)
cout << "\tVisitado\n";
else
cout << "\tNo Visitado\n";
if( !tempCiudad->visitado and tempCiudad->etiquetaB != NULL and tempCiudad->etiquetaA < menorDistancia ){
menorDistancia = tempCiudad->etiquetaA;
caminoCorto = tempCiudad;
cantidadDeLineasEje+=3;
comparaciones+=3;
asignaciones+=2;
}
tempCiudad = tempCiudad->sigV;
cantidadDeLineasEje++;
asignaciones++;
}
caminoCorto->visitado = true;
comparaciones++;
if( caminoCorto->ciudad == destino ){
cout << "\n\nSe encontro el camino corto";
guardarCaminoCorto(caminoCorto);
cantidadDeLineasEje+=3;
comparaciones++;
}
else{
etapa++;
cout << endl << "\n\tEtapa " << etapa << ":";
etiquetaDijkstraDistancia(caminoCorto, destino, tipoBusqueda);
cantidadDeLineasEje++;
}
}
void etiquetaDijkstraDistancia(struct Vertice *camino, char *destino, int tipoBusqueda){
Arco *tempCamino = camino->sigA;
cantidadDeLineasEje++;
asignaciones++;
while( tempCamino != NULL ){
struct Vertice *tempCiudad = getCiudadGrafoAux(tempCamino->destino);
comparaciones++;
cantidadDeLineasEje+=2;
asignaciones++;
if( tempCiudad == NULL ){
cout << "\n\nHa ocurrido un error obteniendo la ciudad destino en el camino de " << tempCamino->origen << " a " << tempCamino->destino;
comparaciones++;
cantidadDeLineasEje+=2;
}
else if( tempCiudad->etiquetaA > camino->etiquetaA + tempCamino->distancia and !tempCiudad->visitado and tipoBusqueda == 1 ){
tempCiudad->etiquetaA = camino->etiquetaA + tempCamino->distancia;
strcpy(tempCiudad->etiquetaB, tempCamino->origen);
comparaciones+=3;
asignaciones+=2;
cantidadDeLineasEje+=3;
}
else if( tempCiudad->etiquetaA > camino->etiquetaA + tempCamino->costo and !tempCiudad->visitado and tipoBusqueda == 2){
tempCiudad->etiquetaA = camino->etiquetaA + tempCamino->costo;
strcpy(tempCiudad->etiquetaB, tempCamino->origen);
comparaciones+=3;
asignaciones+=2;
cantidadDeLineasEje+=3;
}
tempCamino = tempCamino->sigA;
asignaciones++;
cantidadDeLineasEje++;
}
escogerMenorEtiquetadoDijkstraDistancia(destino, tipoBusqueda);
}
bool ryp = false;
int distanciaTotal2 = 0;
bool hayRuta3 = false;
void ruta3(struct Vertice * origen, string destino, string transporte, int distancia){
comparaciones++;
lineasEjecutadas++;
if(origen == NULL)
return;
comparaciones++;
lineasEjecutadas++;
if(origen->visitado == true)
return;
comparaciones++;
lineasEjecutadas++;
push(origen->nombre);
if(origen->nombre == destino){
hayRuta3 = true;
rutaString = "";
imprimir(pila);
lineasEjecutadas+=3;
if(ryp == false){
struct Ramifiacion *nn = new Ramifiacion(rutaString,distanciaTotal2);
nn->sigRamificacion = primeroRamificacion;
primeroRamificacion = nn;
asignaciones+=2;
lineasEjecutadas+=5;
}
else{
struct Ramifiacion *nn = new Ramifiacion(rutaString,distancia);
nn->sigRamificacion = primeroRamificacion;
primeroRamificacion = nn;
distanciaTotal2 = distancia;
asignaciones+=3;
lineasEjecutadas+=5;
}
ryp = true;
asignaciones+=3;
cout<<endl;
lineasEjecutadas+=4;
return;
}
else{
asignaciones++;
origen->visitado = true; /// Lo voy a visitar
struct Arco * tempArco = origen->sigArco;
comparaciones++;
lineasEjecutadas+=4;
while(tempArco!=NULL){
comparaciones++;
lineasEjecutadas++;
if(ryp == false){
comparaciones++;
lineasEjecutadas++;
if(tempArco->tipoTransporte == transporte){
cout<<tempArco->origen<<":"<<tempArco->destino<<":"<<tempArco->distancia<<":"<<tempArco->tipoTransporte<<endl;
distanciaTotal2 = distanciaTotal2 + tempArco->distancia;
lineasEjecutadas+=3;
asignaciones++;
ruta3(buscarVertice(tempArco->destino),destino,transporte,distancia);
tempArco = tempArco->sigArco;
asignaciones++;
lineasEjecutadas+=3;
if(pila->sig!=NULL)
pop(); /// Se coloca aqui porque ya aqui esta en un nuevo camino o ruta
}
else{
tempArco = tempArco->sigArco;
asignaciones++;
lineasEjecutadas+=2;
}
}
else{
comparaciones++;
lineasEjecutadas++;
cout<<tempArco->origen<<":"<<tempArco->destino<<":"<<tempArco->distancia<<":"<<tempArco->tipoTransporte<<endl;
if((tempArco->tipoTransporte == transporte)&&(tempArco->distancia + distancia <= distanciaTotal2)){
distancia = distancia + tempArco->distancia;
lineasEjecutadas+=2;
ruta3(buscarVertice(tempArco->destino),destino,transporte,distancia);
tempArco = tempArco->sigArco;
asignaciones+=2;
lineasEjecutadas+=3;
if(pila->sig!=NULL)
pop();
}
else{
tempArco = tempArco->sigArco;
cout<<"Ramificacion y Poda!"<<endl;
asignaciones++;
lineasEjecutadas+=3;
}
}
}
origen->visitado = false;
asignaciones++;
lineasEjecutadas+=2;
}
}