ALGORITMIA EX2 2015-1 Pregunta 3

#include <stdio.h>
#include <stdlib.h>
#include <float.h>
typedef int TElemento;
typedef struct nodo{
    TElemento elem;
    double peso;
    struct nodo *sig;
}TNodo;

typedef struct lista{
    TNodo *inicio;
    TNodo *fin;
    int numElem;
}TLista;

void Lista_Crear(TLista *L){
    L->inicio = NULL;
    L->fin = NULL;
    L->numElem = 0;
}

int Lista_EstaVacia(TLista L){
    return L.numElem == 0;
}

void Lista_Insertar(TLista *L, TElemento e, double peso){
    TNodo *ptrNuevo = malloc(sizeof(TNodo));
    if (ptrNuevo != NULL){
        ptrNuevo->elem = e;
        ptrNuevo->peso = peso;
        ptrNuevo->sig = NULL;
        // Insertar al final de la lista
        if (Lista_EstaVacia(*L))
            L->inicio = ptrNuevo;
        else
            L->fin->sig = ptrNuevo;
        L->fin = ptrNuevo;
        (L->numElem)++;
    }
}
int Lista_EstaEnLista(TLista L, TElemento e){
    TNodo *ptrRec = L.inicio;
    while (ptrRec!=NULL && ptrRec->elem!=e)
        ptrRec = ptrRec->sig;
    return ptrRec!=NULL;
}

void Lista_Imprimir(TLista L){
    TNodo *ptrRec = L.inicio;
    while(ptrRec != NULL){
        printf("%d ", ptrRec->elem);
        ptrRec = ptrRec->sig;
    }
    printf("\n");
}
typedef struct vertice{
        TElemento info;
        TLista lstAdyacentes;
    struct vertice *sig;
}TVertice;


typedef struct grafo{
    int numVertices;
    TVertice *inicio;
    TVertice *fin;
}TGrafo;

void Grafo_init(TGrafo *grafo){
    grafo->numVertices = 0;
    grafo->inicio = NULL;
    grafo->fin = NULL;
}

int Grafo_existeVertice(TGrafo *grafo, TElemento elem){
    TVertice *ptrRec = grafo->inicio;
    while(ptrRec){
        if (ptrRec->info == elem) return 1;
        ptrRec = ptrRec->sig;
    }
    return 0;
}

void Grafo_insertarVertice(TGrafo *grafo, TElemento elem){
    if (!Grafo_existeVertice(grafo, elem)){
        TVertice *ptrNuevoVert = malloc(sizeof(TVertice));
        if (ptrNuevoVert){
            ptrNuevoVert->info = elem;
            Lista_Crear(&ptrNuevoVert->lstAdyacentes);
            ptrNuevoVert->sig = grafo->inicio;

            grafo->inicio= ptrNuevoVert;
            if (grafo->numVertices == 0)
                grafo->fin = ptrNuevoVert;
            grafo->numVertices++;
        }
    }
}

void Grafo_insertarArista(TGrafo *grafo, TElemento elem1, TElemento elem2, double peso){
    if (Grafo_existeVertice(grafo, elem1) && Grafo_existeVertice(grafo, elem2)){
        TVertice *ptrRec = grafo->inicio;
        while(ptrRec){
            if (ptrRec->info ==  elem1){
                if (!Lista_EstaEnLista(ptrRec->lstAdyacentes, elem2))
                    Lista_Insertar(&ptrRec->lstAdyacentes, elem2, peso);
                break;
            }
            ptrRec = ptrRec->sig;
        }
    }
}

void Grafo_imprimirGrafo(TGrafo *grafo){
    TVertice *ptrRec = grafo->inicio;
    while (ptrRec){
        printf("%d: ", ptrRec->info);
        Lista_Imprimir(ptrRec->lstAdyacentes);
        ptrRec = ptrRec->sig;
    }
}

TLista *ObtenerAdyacentes(TGrafo *grafo, TElemento elem){
    TVertice *ptrRec = grafo->inicio;
    while(ptrRec){
        if (ptrRec->info == elem){
            return &(ptrRec->lstAdyacentes);
        }
        ptrRec = ptrRec->sig;
    }
}

int ObtenerMinimoNoVisitado(TGrafo *grafo,int *arrVisitados, double *arrDistMin){
    int i, indMin; double minDist = DBL_MAX;
    for (i = 0; i < grafo->numVertices; i++){
        if (arrVisitados[i] == 0 && arrDistMin[i] < minDist){
            minDist = arrDistMin[i];
            indMin = i;
        }
    }
    return indMin;
}

void Grafo_imprimirCaminosMasCortos(TGrafo *grafo, TElemento vertInicial,TElemento vertFinal){
    int *arrPadres = malloc(grafo->numVertices*sizeof(int));
    int *arrVisitados = malloc(grafo->numVertices*sizeof(int));
    double *arrDistMin = malloc(grafo->numVertices*sizeof(double));

    int i;
    for (i = 0; i < grafo->numVertices; i++){
        arrPadres[i] = -1;
        arrVisitados[i] = 0;
        arrDistMin[i] = DBL_MAX;
    }
   arrDistMin[vertInicial-1] = 0;

    int indMin; TLista *lstAdyacentes;
    for (i=0; i < grafo->numVertices; i++){
        //Encontrar el mínimo de los no visitados
        indMin = ObtenerMinimoNoVisitado(grafo, arrVisitados, arrDistMin);
        arrVisitados[indMin] = 1;
        lstAdyacentes = ObtenerAdyacentes(grafo, indMin + 1);
        TNodo *ptrNodo = lstAdyacentes->inicio;
        while (ptrNodo){
            if (arrVisitados[ptrNodo->elem - 1] == 0)
                if ( arrDistMin[ptrNodo->elem - 1] > arrDistMin[indMin] + ptrNodo->peso){
                    arrDistMin[ptrNodo->elem - 1] = arrDistMin[indMin] + ptrNodo->peso;
                    arrPadres[ptrNodo->elem - 1] = indMin;
                }
            ptrNodo = ptrNodo->sig;
        }
    }

    if (arrDistMin[vertFinal-1]!=DBL_MAX)
        printf("%.0lf\n", arrDistMin[vertFinal-1]);
    else
        printf("unreachable\n");

}

int main(){
    int c,m,n,s,t,ar1,ar2;
    float p;
    TGrafo G;
    scanf("%d",&c);
    int i,j;
    for (i=1;i<=c;i++){
        Grafo_init(&G);
        scanf("%d%d%d%d",&m,&n,&s,&t);
        for (j=0;j<m;j++)
            Grafo_insertarVertice(&G,j+1);
        for (j=0;j<n;j++){
            scanf("%d%d%f",&ar1,&ar2,&p);
            Grafo_insertarArista(&G,ar1+1,ar2+1,p);
            Grafo_insertarArista(&G,ar2+1,ar1+1,p);
        }
        printf("Case #%d: ",i);
        Grafo_imprimirCaminosMasCortos(&G,s+1,t+1);
    }
}