Algoritmo de Dijkstra e Algoritmo Guloso

#include <stdio.h>
#include <stdlib.h>
#define bool int
#define dado int

typedef struct Nodo {
    dado data;
    //int distance;
    //int index1;
    //int index2;
} Nodo;

typedef struct Aresta {
    Nodo *nodoSource, *nodoFinal;
    bool flag_valid;
    int value;
} Aresta;

void initializeMatriz(Aresta **aresta, int tam)
{
    int i, j;
    for (i=0; i<tam; i++)
    {
        for (j=0; j<tam; j++)
        {
            aresta[i][j].flag_valid = 0;
            aresta[i][j].nodoSource = NULL;
            aresta[i][j].nodoFinal = NULL;
            aresta[i][j].value = 0;
        }
    }
}

void initializeNodo(Nodo *nodo, int i)
{
    //nodo->distance = 2000000000;
    //nodo->index1 = 0;
    //nodo->index2 = 0;
    nodo->data = i;
}

bool addNodo(Aresta **aresta, int i, int tam)
{
    int j;
    Nodo *aux;
    if (aresta[i][0].nodoSource != NULL)
    {
        printf("Erro: o nodo ja existe! Reiniciando...");
        return 0;
    }

    aux = malloc(sizeof(Nodo));
    if (aux == NULL)
    {
        printf("Erro: o nodo nao pode ser alocado! Reiniciando...");
        return 0;
    }
    initializeNodo(aux, i);
    for (j=0; j<tam; j++)
    {
        aresta[i][j].nodoSource = aux;
        aresta[j][i].nodoFinal = aux;
    }
    return 1;
}

void addAresta(Aresta **aresta, int i, int j, int peso)
{
    if (aresta[i][0].nodoSource == NULL || aresta[j][0].nodoSource == NULL)
    {
        printf("Erro: um dos nodos nao existe! Reiniciando...");
        return;
    }
    if (aresta[i][j].flag_valid == 1)
    {
        printf("Erro: ja existe uma aresta! Reiniciando...");
        return;
    }
    if (i == j)
        aresta[i][j].value = 0;
    else
        aresta[i][j].value = peso;
    aresta[i][j].flag_valid = 1;
    return;
}

void searchDijkstra(Aresta **aresta, int origem, int destino, int tam)
{

    int i, k=-1, aux1, aux2 = 2000000000, valor[tam], vetor[tam], anterior[tam];
    for (i=0; i<tam; i++)
    {
        if (aresta[origem][i].flag_valid == 1)
        {
            anterior[i] = origem;
            valor[i] = aresta[origem][i].value;
        }
        else
        {
            anterior[i] = 0;
            valor[i] = aux2;
        }
        vetor[i]=0;
    }
    vetor[origem] = 1;
    valor[origem] = 0;

    do
    {
        aux1 = aux2;
        for (i=0; i<tam; i++)
        {
            if (!vetor[i])
            {
                if (valor[i] >= 0 && valor[i] < aux1)
                {
                    aux1 = valor[i];
                    k = i;
                }
            }
        }

        if (aux1 != aux2 && k != destino)
        {
            vetor[k] = 1;
            for (i=0; i<tam; i++)
            {
                if (!vetor[i])
                {
                    if (aresta[k][i].flag_valid == 1 && valor[k]+aresta[k][i].value < valor[i])
                    {
                        valor[i] = valor[k] + aresta[k][i].value;
                        anterior[i] = k;
                    }
                }
            }
        }
    }
    while (k != destino && aux1 != aux2);

    if (aux1 == aux2)
    {
        printf("Erro: nao existe caminho entre os nodos %d e %d", origem, destino);
        return;
    }

    printf("O caminho mais curto e: ");
    i = destino;
    printf("%d", i);
    i = anterior[i];
    while (i != 0)
    {
        printf("<-%d", i);
        i = anterior[i];
    }
    printf("\nO custo deste caminho e: %d\n", valor[destino]);
}

void searchGuloso(Aresta **aresta, int origem, int destino, int tam)
{
    int i, k, aux1, aux2 = 2000000000, valor[tam], vetor[tam], anterior[tam];

    for (i=0; i<tam; i++)
    {
        if (aresta[origem][i].flag_valid == 1)
        {
            anterior[i] = origem;
            valor[i] = aresta[origem][i].value;
        }
        else
        {
            anterior[i] = 0;
            valor[i] = aux2;
        }
        vetor[i]=0;
    }
    vetor[origem] = 1;
    valor[origem] = 0;

    do
    {
        aux1 = aux2;
        for (i=0; i<tam; i++)
        {
            if (!vetor[i])
            {
                if (valor[i] >= 0 && valor[i] < aux1)
                {
                    aux1 = valor[i];
                    k = i;
                }
            }
        }

        if (aux1 != aux2 && k != destino)
        {
            vetor[k] = 1;
            for (i=0; i<tam; i++)
            {
                if (!vetor[i])
                {
                    if (aresta[k][i].flag_valid == 1 && valor[i] < aresta[k][i].value)
                    {
                        valor[i] = valor[k] + aresta[k][i].value;
                        anterior[i] = k;
                    }
                }
            }
        }

    }
    while (k != destino && aux1 != aux2);

    if (aux1 == aux2)
    {
        printf("Erro: nao existe caminho entre os nodos %d e %d", origem, destino);
        return;
    }

    printf("O caminho mais rapido e: ");
    i = destino;
    printf("%d", i);
    i = anterior[i];
    while (i != 0)
    {
        printf("<-%d", i);
        i = anterior[i];
    }
    printf("\nO custo deste caminho e: %d\n", valor[destino]);
}

void main()
{
    int i, j, select, tam, nodo_count=0;
    Redo: printf("Digite a quantidade de nodos a armazenar: ");
    do{
        scanf("%d", &tam);
    }while(tam <= 0 || tam > 20);
    Aresta **aresta = malloc(tam*sizeof(Aresta*));
    for (i=0; i<tam; i++)
        aresta[i] = malloc(tam*sizeof(Aresta));
    initializeMatriz(aresta, tam);
    printf("\n\n");

    //--------- Testes pré-prontos
    /*
    if(!addNodo(aresta,1,tam)){aresta=aresta;}
    if(!addNodo(aresta,2,tam)){aresta=aresta;}
    if(!addNodo(aresta,3,tam)){aresta=aresta;}
    addAresta(aresta,1,2,8);
    addAresta(aresta,2,3,2);
    addAresta(aresta,1,3,11);

    searchDijkstra(aresta,1,3,tam);
    printf("\n\n");
    searchGuloso(aresta,1,3,tam);
    printf("\n\n");
    */

    Do: printf("\n\nEscolha... \n1 para adicionar um nodo\n2 para adicionar uma aresta\n3 para buscar o caminho mais curto entre dois nodos\n4 para buscar o caminho mais barato entre dois nodos\n5 para refazer a matriz\n6 para sair\nDigite: ");
    scanf("%d", &select);
    switch(select)
    {
        case 1:
            if (nodo_count == tam)
            {
                printf("Erro: a capacidade de nodos ja foi alcancada! Reiniciando...");
                goto Do;
            }
            printf("Digite o indice do nodo: ");
            scanf("%d", &i);
            if (i < 0 || i >= tam)
            {
                printf("Erro: indice invalido! Reiniciando...");
                goto Do;
            }
            if (addNodo(aresta,i,tam))
                nodo_count++;
            goto Do;
        break;

        case 2:
            if (nodo_count < 2)
            {
                printf("Erro: existem menos que 2 nodos. Reiniciando...");
                goto Do;
            }
            printf("Digite o indice do nodo origem e o indice do nodo destino: ");
            scanf("%d%d", &i, &j);
            if (i < 0 || j < 0 || i >= tam || j >= tam)
            {
                printf("Erro: indices invalidos! Reiniciando...");
                goto Do;
            }

            printf("Digite o peso da aresta: ");
            scanf("%d", &select);
            if (select <= 0)
            {
                printf("Erro: o peso nao deve ser negativo! Reiniciando...");
                goto Do;
            }
            addAresta(aresta,i,j,select);
            goto Do;
        break;

        case 3:
            if (nodo_count < 2)
            {
                printf("Erro: existem menos que 2 nodos! Reiniciando...");
                goto Do;
            }
            printf("Digite o indice do nodo origem e o indice do nodo destino: ");
            scanf("%d%d", &i, &j);
            if (i < 0 || j < 0 || i >= tam || j >= tam)
            {
                printf("Erro: indices invalidos! Reiniciando...");
                goto Do;
            }

            searchDijkstra(aresta,i,j,tam);
            goto Do;
        break;

        case 4:
            if (nodo_count < 2)
            {
                printf("Erro: existem menos que 2 nodos! Reiniciando...");
                goto Do;
            }
            printf("Digite o indice do nodo origem e o indice do nodo destino: ");
            scanf("%d%d", &i, &j);
            if (i < 0 || j < 0 || i >= tam || j >= tam)
            {
                printf("Erro: indices invalidos! Reiniciando...");
                goto Do;
            }

            searchGuloso(aresta,i,j,tam);
            goto Do;
        break;

        case 5:
            for (i=0; aresta[i][0].nodoSource == NULL; i++)
                if (i == tam-1)
                    goto Next;
            free(aresta[i][0].nodoSource);

            for (j=0; j<tam; j++)
            {
                if (aresta[i][j].nodoFinal != NULL)
                    free(aresta[i][j].nodoFinal);
            }
            Next: for (i=0; i<tam; i++)
                free(aresta[i]);
            free(aresta);
            printf("\n\n\n------------------------\n\n");
            goto Redo;
        break;

        case 6:
            for (i=0; aresta[i][0].nodoSource == NULL; i++)
                if (i == tam-1)
                    goto Finish;
            free(aresta[i][0].nodoSource);

            for (j=0; j<tam; j++)
            {
                if (aresta[i][j].nodoFinal != NULL)
                    free(aresta[i][j].nodoFinal);
            }
            Finish: for (i=0; i<tam; i++)
                free(aresta[i]);
            free(aresta);
            exit(1);
        break;

        default:
            goto Do;
        break;
    }
}