Código de C/Visual C - Algoritmo de prim y dijkstra

Algoritmo de prim y dijkstragráfica de visualizaciones


C/Visual C

estrellaestrellaestrellaestrellaestrella(10)
Publicado el 19 de Diciembre del 2010 por Marcelo Tabango
11.226 visualizaciones desde el 19 de Diciembre del 2010. Una media de 42 por semana
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

Versión 1
estrellaestrellaestrellaestrellaestrella(10)

Publicado el 19 de Diciembre del 2010gráfica de visualizaciones de la versión: Versión 1
11.227 visualizaciones desde el 19 de Diciembre del 2010. Una media de 42 por semana
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

Si alguno de los archivos de descarga no funciona, comentanos aquí el error.




Comentarios sobre la versión: Versión 1 (10)

Jose
05 de Enero del 2011
estrellaestrellaestrellaestrellaestrella
ME gusto mucho tu trabajo bien estructurado y no te enrredaste con funciones demaciado complicadas muy buen uso de los algritmos de prim y dijkstra
Responder
Cutberto Medina
28 de Abril del 2011
estrellaestrellaestrellaestrellaestrella
Gracias por compartir esta información.
Responder
Paola
23 de Marzo del 2012
estrellaestrellaestrellaestrellaestrella
Gracias por compartir la informacion
Responder
Manuel
22 de Junio del 2013
estrellaestrellaestrellaestrellaestrella
Era lo que necesitaba, excelente trabajo, Gracias por compartir tú trabajo.
Responder
Hernan
17 de Marzo del 2014
estrellaestrellaestrellaestrellaestrella
gracias x la ayuda
Responder
Obed
08 de Octubre del 2014
estrellaestrellaestrellaestrellaestrella
Gracias por los datos.
Responder
arzuaga
02 de Noviembre del 2014
estrellaestrellaestrellaestrellaestrella
no puedo hacer que corra el prim y como le harías para que que lea una matriz de un archivo txt
Responder
jessica
16 de Diciembre del 2014
estrellaestrellaestrellaestrellaestrella
sera que lo podes hacer en visual Studio 2012 c#.. gracias
Responder
Carlos
17 de Junio del 2015
estrellaestrellaestrellaestrellaestrella
int etapa = 1;
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);
}
Responder
Carlos
17 de Junio del 2015
estrellaestrellaestrellaestrellaestrella
Hey, aqui tengo uno que utiliza la ramificacion y poda, talvez ayude!

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;
}
}
Responder

Comentar la versión: Versión 1

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios

http://lwp-l.com/s2013