distancia_cidades3.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <stdbool.h>
#include <limits.h>

int dijkstra(int qt_cidades, int graph[qt_cidades][qt_cidades], int src, int destino_index, char cidades[][21]);

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

void impime_matriz(int qt_cidades, int matriz[qt_cidades][qt_cidades], int tamanho_linha, int tamanho_coluna){
    printf("\n\n");
    for (int i = 0; i < tamanho_linha; i++){
        for(int j = 0; j < tamanho_coluna; j++){
            printf("  %d  ", matriz[i][j]);
        }
        printf("\n");
    }
}


int main(int argc, char *argv[]){
    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");
        return(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 Dijkstra, 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!");
        return 2;
    }
    if (destino_index == -1){
        printf("\n Cidade de destino não encontrada!");
        return 3;
    }

    /// Chama a função dijkstra e imprime a menor distância
    printf("Menor percurso: ");
    int resposta = dijkstra(qt_cidades, grafo, origem_index, destino_index, cidades);
    printf("%s\n", cidades[destino_index]);
    printf("Distancia total: %d Km", resposta);

    /// Fecha
    fclose(arquivo);
    return 0;
}


/*
    Abaixo, o algoritmo de Dijkstra. Tal algoritmo foi retirado do site
    Geeks for Geeks, e pode ser acessado pelo link:
    https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

    Originalmente sua implementação não previa informar o menor caminho (os nomes das
    cidades), apenas a menor distância, além de estar em C++. Com algumas modirficações,
    foi adicionada tal funcionalidade e compatibilidade com C.
*/

// A C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

//#include <limits.h>
//#include <stdio.h>

// Number of vertices in the graph
//#define V 5

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[], int V)
{
    // Initialize min value
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++){
        if (sptSet[v] == false && dist[v] <= min){
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

// A utility function to print the constructed distance array
void printSolution(int dist[], int V)
{
    printf("\n\nVertex \t\t Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t %d\n", i, dist[i]);
}

// Function that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
int dijkstra(int qt_cidades, int graph[qt_cidades][qt_cidades], int src, int destino_index, char cidades[][21])
{
    int V = qt_cidades;
    int dist[V]; // The output array. dist[i] will hold the shortest
    // distance from src to i

    bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
    // path tree or shortest distance from src to i is finalized

    // Initialize all distances as INFINITE and stpSet[] as false
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;

    // Distance of source vertex from itself is always 0
    dist[src] = 0;

    char vetor_menor_percurso[V][21];
    int vetor_menor_percurso_dist[V];
    int auxiliar2 = 0;

    // Find shortest path for all vertices
    for (int count = 0; count < V - 1; count++) {
        // Pick the minimum distance vertex from the set of vertices not
        // yet processed. u is always equal to src in the first iteration.
        int u = minDistance(dist, sptSet, V);

        // Mark the picked vertex as processed
        sptSet[u] = true;


        int auxiliar = 0;
        // Update dist value of the adjacent vertices of the picked vertex.
        for (int v = 0; v < V; v++){

            // Update dist[v] only if is not in sptSet, there is an edge from
            // u to v, and total weight of path from src to v through u is
            // smaller than current value of dist[v]
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                && dist[u] + graph[u][v] < dist[v]){
                dist[v] = dist[u] + graph[u][v];
            }

            /// Inicialmente esse código só mostrava a distância total final,
            /// então foram necessárias algumas modificações para que
            /// ele também fosse registrando as cidades do menor caminho
            if (auxiliar == destino_index){
                strcpy(vetor_menor_percurso[auxiliar2], cidades[u]);
                vetor_menor_percurso_dist[auxiliar2] = dist[destino_index];
                auxiliar2++;
            }
            auxiliar++;

        }

    }

    int i = 0;
    do{
        printf("%s ", vetor_menor_percurso[i]);
        i++;
    }while(vetor_menor_percurso_dist[i-1] != dist[destino_index]);

//  // print the constructed distance array
//  printSolution(dist, int V);

    return dist[destino_index];

}