ijert-dijkstra3.c

/* TO FIND THE SHORTEST PATH OF A GRAPH USING DJIKSTRA ALGORITHM */
#include<stdio.h>
#include<limits.h>/* Maximum Number of Nodes in a Graph */

/// Bibliotecas adicionadas por mim
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
/// ---

#define MAXNODE 10  // Número máximo de Cidades: 9 (uma a menos)
#define PERM 1
#define TENT 2
#define infinity INT_MAX  // Inteiro máximo



typedef struct NODELABEL
{
    int predecessor;
    int length; /* Optimal distance from Source */
    int label; /* label is tentative or permanent */
}NODELABEL;


/*
    A função abaixo foi retirada do artigo "Implementation Of Shortest Path Algorithm Using In C"
    publicado no International Journal of Engineering Research & Technology por P.Manikandan e S.Yuvarani,
    e pode ser acessado através do endereço eletrônico abaixo:
    https://www.ijert.org/research/implementation-of-shortest-path-algorithm-using-in-c-IJERTV2IS60569.pdf
*/
/*
    Function: Short path Prototype:int Short Path(a, n, s, t, path, dist)

    Input:a-Adjacency Matrix   describing   the graph n-Number of Nodes in the graphs-Source Nodet-Target Node or Sink Node

    Output:Path -list  of  optimal  path  from source   to sink   dist -Minimum   Distance between source and sink

    Returns:0 -if   there   is   no   path   count indicating  the  number  of  nodes  along  the optimal path, otherwise
*/
int ShortPath( a, n, s, t, path, dist )
int  a[MAXNODE][MAXNODE], n, s, t, path [MAXNODE], *dist;
{
    NODELABEL state[MAXNODE];int i, k, min, count;
    int rPath[MAXNODE];
    *dist=0;
    /* Initialize all nodes as tentative nodes */
    for(i=1; i<=n; i++){
            state[i].predecessor=0;
            state[i].length=infinity;
            state[i].label=TENT;
    }/* Make source Node as Permanent */
    state[s].predecessor=0;
    state[s].length=0;state[s].label=PERM;
    /* Start from source node */
    k=s;
    do{/* Check all the paths from Kth node and find their distanceform K node */
        for(i=1; i<=n; i++){
            /* -ve if no direct path, 0 if to the same otherwise directpath */
            if(a[k][i]>0 && state[i].label==TENT){
                if(state[k].length+a[k][i]<state[i].length){
                    state[i].predecessor=k;state[i].length=state[k].length+a[k][i];
                }
            }
        }/* Find the tentatively labeled node with smaller cost */
        min=infinity;
        k=0;
        for(i=1; i<=n; i++){
            if(state[i].label==TENT && state[i].length<min){
                min=state[i].length;k=i;
            }
        }/* Is Source Or Sink Node is Isolated */
        if(k==0)
            return(0);
        state[k].label=PERM;
    }while(k!=t);/* Store Optimal Path */
    k=t;
    count=0;
    do{
        count = count + 1;
        rPath[count]=k;
        k=state[k].predecessor;
    }while(k!=0);/* Reverse nodes since algorithm stores path in reversedirection */

    for(i=1; i<=count; i++)
        path[i]=rPath[count-i+1];
    for(i=1; i<count; i++)
        *dist+=a[path[i]][path[i+1]];

    return(count);
}
/* Fim da função ShortPath */


typedef struct{
    char cidade1[21];
    char cidade2[21];
    int distancia;
} Rota;


int verifica_se_esta_no_vetor(char vetor[][21], char palavra[], int tamanho_do_vetor){

    for (int i = 0; i < tamanho_do_vetor; i++){
        if (strcmp(palavra, vetor[i]) == 0){
            return 1;
        }
    }

    return 0;
}

int procura_caminhos_entre_cidades(Rota rotas_ptr[], char cidade1[], char cidade2[], int arestas){

    for(int i = 0; i < arestas; i++){
        if (strcmp((rotas_ptr + i)->cidade1, cidade1) == 0 && strcmp((rotas_ptr + i)->cidade2, cidade2) == 0){
            return (rotas_ptr + i)->distancia;
        }
    }

    return 0;
}


/// MAIN

void main(){


    printf("Digite o nome do arquivo de entrada: ");
    char nome_do_arquivo[100];
    scanf("%s", &nome_do_arquivo[0]);
//  char nome_do_arquivo[] = "teste.txt";

    /// Abre o arquivo e verifica se foi ok
    FILE *arquivo;
    arquivo = fopen(nome_do_arquivo, "r");
    if (arquivo == NULL){
        printf("Erro na abertura do aqruivo\n");
        exit(1);
    }

    int arestas = 0;

    /// Armazena a primeira linha do arquivo de entrada
    fscanf(arquivo, "%d", &arestas);

    Rota *rotas_ptr = (Rota*) malloc(arestas * sizeof(Rota));

    /// Continua lendo o arquivo com as entradas e armazenando os valores
    for(int i = 0; i < arestas; i++){

        fscanf(arquivo, "%s", (rotas_ptr + i)->cidade1);
        fscanf(arquivo, "%s", (rotas_ptr + i)->cidade2);
        fscanf(arquivo, "%d", &(rotas_ptr + i)->distancia);

    }

    int qt_cidades = 0;
    char cidades[1000][21]; // Número máximo de cidades: 1000

    /// Preenche um vetor com os nomes das cidades

    ///     Para as cidades à esquerda no arquivo
    for(int i = 0; i < arestas; i++){
        char cid[21];

        strcpy(cid, (rotas_ptr + i)->cidade1);

        /// Verifica se a cidade já foi adicionada ao vetor
        int v = verifica_se_esta_no_vetor(cidades, cid, arestas);
        if (v == 0){
            strcpy(cidades[qt_cidades], cid);
            qt_cidades++;
        }
    }

    ///     Para as cidades à direita no arquivo
    for(int i = 0; i < arestas; i++){
        char cid[21];

        strcpy(cid, (rotas_ptr + i)->cidade2);

        /// Verifica se a cidade já foi adicionada ao vetor
        int v = verifica_se_esta_no_vetor(cidades, cid, arestas);
        if (v == 0){
            strcpy(cidades[qt_cidades], cid);
            qt_cidades++;
        }
    }

    /// Lê as cidades de origem e destino e atribui o valor
    char origem[21] = "";
    char destino[21] = "";

    fscanf(arquivo, "%s", origem);
    fscanf(arquivo, "%s", destino);

    // Cria a matriz/ grafo
    int (*grafo)[qt_cidades] = malloc(qt_cidades * qt_cidades * sizeof(grafo[0][0]));

    // Preenche a matriz/ grafo inicialmente com zeros
    for (int i = 0; i < qt_cidades; i++){
        for(int j = 0; j < qt_cidades; j++){
            grafo[i][j] = 0;
        }
    }

    /// Este FOR preenche a matriz/ grafo com as distâncais entre as cidades (caminhos)
    for (int i = 0; i < qt_cidades; i++){
        char linha[21];
        strcpy(linha, cidades[i]);

        for(int j = 0; j < qt_cidades; j++){
            char coluna[21];
            strcpy(coluna, cidades[j]);

            /// Procura a distâncias entre todas as cidades e preenche todas as
            /// posições da matriz (tanto superior quanto inferior)
            int dist = procura_caminhos_entre_cidades(rotas_ptr, linha, coluna, arestas);

            if (grafo[i][j] < dist)
                grafo[i][j] = dist;

            if (grafo[j][i] < dist)
                grafo[j][i] = dist;

        }
    }

    /// Identifica a cidade de origem e a cidade de destino por meio de índices.
    /// Esses índices serão passados para a função ShortPath, que já funcionava
    /// de tal maneira
    int origem_index = -1;
    int destino_index = -1;
    for (int i = 0; i < qt_cidades; i++){
        if (strcmp(origem, cidades[i]) == 0){
            origem_index = i;
        }
        if (strcmp(destino, cidades[i]) == 0){
            destino_index = i;
        }
    }
    if (origem_index == -1){
        printf("\n Cidade de origem não encontrada!");
        exit(2);
    }
    if (destino_index == -1){
        printf("\n Cidade de destino não encontrada!");
        exit(3);
    }
    if (origem_index == destino_index){
        printf("Menor percurso:");
        printf(" %s",cidades[origem_index]);
        printf("\nDistancia total: 0 Km\n");
        exit(4);
    }

    /// Copia a matriz, deslocando uma unidade para baixo e para a direita
    /// para então passar a matriz copiada para a função ShortPath

    int from, to, dist,count, n;


    int a[MAXNODE][MAXNODE];
    int path[MAXNODE];


    for (int i = 0; i < qt_cidades; i++){
        for (int j = 0; j < qt_cidades; j++){
            a[i+1][j+1] = grafo[i][j];
        }
    }

    /// Chama a função ShortPath e imprime a menor distância
    count = ShortPath(a,qt_cidades,origem_index+1, destino_index+1, path, &dist);
    if(dist){
        printf("Menor percurso:");
        printf(" %s",cidades[origem_index]);
        for(int i=2;i<=count;i++)
            printf(" %s",cidades[path[i]-1]);
        printf("\nDistancia total: %d Km\n", dist);
    }
    else
        printf("\n Path does not exist \n");
}