Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
#include <stdio.h> #include <stdlib.h> #include <limits.h> //////////////////////////////////////////////// // CEFET/RJ UnED Petrópolis // // Bernardo Costa // // Estrutura de Dados II // // Dijkstra // // Professora Laura Assis // //////////////////////////////////////////////// int **MatrizAdjacencia(int v); void LerDadosMatrizAdjacencia(int a, int **ma, int *origem, int *destino, int *prioridade); void ImprimirMatrizAdjacencia(int v, int **ma); void dijkstra(int **agm, int v, int a, int **ma, int *origem, int *destino, int *usados, int inicio, int *prioridade); int testePrioridade(int *prioridade, int a); int main(){ int i, j, k; int v, a, inicio; inicio = 0; int op; int **ma, **agm; //ponteiro para matriz adjacencia ma = NULL; scanf("%d %d %d", &v, &a, &inicio); int prioridade[a]; for(i = 0; i<a;i++){ prioridade[i] = INT_MAX; } int usados[v]; int origem [a]; int destino [a]; ma = MatrizAdjacencia(v); agm = MatrizAdjacencia(v); LerDadosMatrizAdjacencia(a, ma, origem, destino, prioridade); printf("\n\nGrafo Inicial \n"); printf("___________________\n\n"); ImprimirMatrizAdjacencia(v, ma); printf("___________________\n\n"); dijkstra(agm, v, a, ma, origem, destino, usados, inicio, prioridade); return 0; } int **MatrizAdjacencia(int v) { int **ma; int i; ma = (int **) calloc(v, sizeof(int*)); if(ma == NULL) { printf("\nErro ao reservar memória\n"); exit(0); } for(i = 0; i<v;i++) { ma[i] = calloc(v, sizeof(int)); if(ma[i] == NULL) { printf("\nErro ao reservar memória para ma[%d]\n", i); exit(1); } } return ma; } void LerDadosMatrizAdjacencia(int a, int **ma, int *origem, int *destino, int *prioridade) { int i, j, k, peso; for(k = 0;k < a; k++) { scanf("%d %d %d", &i, &j, &peso); prioridade[k] = peso; origem[k] = i-1; destino[k] = j-1; if(i == j) { ma[i-1][j-1] = peso; } else { ma[i-1][j-1] = peso; } } } void ImprimirMatrizAdjacencia(int v, int **ma) { int i, j; for(i=0;i<v;i++) { for(j=0;j<v;j++){ printf(" %d ", ma[i][j]); } printf("\n"); } } void dijkstra(int **agm, int v, int a, int **ma, int *origem, int *destino, int *usados, int inicio, int *prioridade){ int i, j, k, c; c =0; int pai[v]; int custo[v]; int peso[v]; int S[v]; int menor = INT_MAX; if (inicio == 0){ inicio = 1; } inicio --; for(i = 0; i < v; i++){ pai[i] = -1; peso[i] = INT_MAX; S[i] = 0; } k = 0; pai[inicio] = -2; //inicio não tem pai peso[inicio] = 0; for(i = 0; i < v; i++){ usados[i] = 0; } usados[inicio] = 1; // vai ser o incio, então ele está automaticamente usado! printf("\n\n ** Dijkstra **\n"); int o, aux, l, m, cont = 0; S[cont] = inicio+1; int x = cont; for(i = 0; i < a; i++){ for(o = 0; o < a; o++){ if((usados[origem[o]] == 1)&&(prioridade[o] != INT_MAX)) { menor = prioridade[o]; k = o; break; } } aux = peso[origem[k]] + menor; if(peso[destino[k]] > aux ){ peso[destino[k]] = aux; pai[destino[k]] = origem[k]; usados[destino[k]] = 1; usados[origem[k]] = 1; prioridade[k] = INT_MAX; } else{ prioridade[k] = INT_MAX; } int help = 0; for(m = 0;m<v;m++){ if(S[m] == destino[k]+1){ help++; } } if(help == 0){ x++; S[x] = destino[k]+1; } printf("\n\n____________________\n\nInteração = %d\n\nPesos:\t", cont+1); for(l = 0; l < v; l++){ if(peso[l] == INT_MAX){ printf("(∞)\t"); } else{ printf("(%d)\t", peso[l]); } } printf("\nPai:\t"); for(m = 0; m < v; m++){ printf("(%d)\t", pai[m]+1); } printf("\nS:\t"); for(l = 0; l < v; l++){ if(S[l] == 0){ printf("( )\t"); } else{ printf("(%d)\t", S[l]); } } cont ++; } printf("\n____________________\n\n\n"); } int testePrioridade(int *prioridade, int a){ int i, b = 0; for(i = 0; i< a; i++){ if (prioridade[i] != INT_MAX){ b++; } } if (b) return 1; else{ return 0; } }
Compartilhar