Buscar

dijkstra em c

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

Teste o Premium para desbloquear

Aproveite todos os benefícios por 3 dias sem pagar! 😉
Já tem cadastro?

Outros materiais

Materiais relacionados

Perguntas relacionadas

Perguntas Recentes