Segmentation fault na função de extrair o mínimo do heap

[eduarda-nicoletto]

Olá! Durante a implementação do algoritmo de Dijkstra, eu usei uma função que extrai o vértice que é o mínimo do heap. Quando compilei, o erro de segmentation fault apareceu. Aí eu fui testando e identifiquei que o erro acontece nessa função de mínimo, mais especificamente no momento que tento decrescer a qtd de elementos no heap. Coloquei a função de descer no heap commo comentário para garantir que o erro não era nela. Se eu tiro a linha f->qtd--; do programa, ele funciona mas se eu coloco ele, dá o erro 139. Coloquei aqui em baixo a função e a definição da fila de prioridades. Alguém saberia me ajudar a descobrir como resolver isto?

int min(p_fp f){
    Item aux=f->fila[0];
    f->fila[0]=f->fila[f->qtd-1];
    f->fila[f->qtd-1]=aux;
    f->qtd--;
    //desce_heap(f, 0);
    return aux.local;
}

//DEFINIÇÃO DE FILA DE PRIORIDADE E SEUS ITENS
typedef struct{
    int local, chave; //vertices, prioridades
}Item;

typedef struct{
    Item *fila; //vetor de itens
    int qtd, tamanho,*i; //qtd de elementos, tamanho, indice
}FilaP;
typedef FilaP *p_fp;

[iagoac]

@eduarda-nicoletto eu não consigo testar seu código somente com este pequeno exemplo que temos aqui.

Para quê você utiliza as variáveis tamanho e qtd na struct FilaP? Meu primeiro chute é que você está fazendo confusão entre as duas em alguma outra função.

Também tente trocar f->qtd-- por *f->qtd--. Eu não tenho realmente certeza que seja isso, mas, não custa tentat neh?

[eduarda-nicoletto]

@iagoac eu mudei um pouco o programa mas ainda está dando segmentation fault. Fui na monitoria de agora e o PAD conseguiu identificar que o erro está no retorno da minha função prioridade, provavelmente devido a alguma confusão com os índices dos vetores e a atribuição dos vértices. Estou revisando tudo que envolve a fila de prioridades mas não consigo encontrar o erro. Poderia me ajudar? Vou enviar meu programa.

include

include

//DEFINIÇÃO DE GRAFO E SEUS NÓS typedef struct Noh{ int local, tempo; //vertices, pesos struct Noh vizinho; //prox }Noh; typedef struct Noh p_no;

typedef struct{ p_no mapa; //matriz de adjacencia int sz; //tamanho da matriz }Grafo; typedef Grafo p_grafo;

//DEFINIÇÃO DE FILA DE PRIORIDADE E SEUS ITENS typedef struct{ int local, chave; //vertices, prioridades }Item;

typedef struct{ Item fila; //vetor de itens int index; int qtd, tamanho; //qtd de elementos, tamanho, indice }FilaP; typedef FilaP *p_fp;

//CRIANDO GRAFO p_grafo criar_grafo(int tamanho){ p_grafo grafo; grafo=malloc(sizeof(Grafo)); grafo->sz=tamanho; grafo->mapa=calloc(tamanho,sizeof(Noh)); return grafo; }

//CRIANDO FILA DE PRIORIDADES p_fp criar_fila(int sz){ p_fp FP=malloc(sizeof(FilaP)); FP->fila=malloc(szsizeof(Item)); FP->index=malloc(szsizeof(int)); FP->qtd=0; FP->tamanho=sz; return FP; }

//INSERINDO ARESTA NO GRAFO p_no insere_vizinhos(p_no lista, int z, int peso){ p_no novo=malloc(sizeof(Noh)); novo->vizinho=lista; novo->local=z; novo->tempo=peso; return novo; } void insere_aresta(p_grafo g, int x, int y, int peso){ g->mapa[x]=insere_vizinhos(g->mapa[x], y, peso); g->mapa[y]=insere_vizinhos(g->mapa[y], x, peso); }

//INSERINDO ITENS NA FILA DE PRIORIDADES

define pai(i) (i-1)/2

void up_heap(p_fp f, int n){ Item aux; if(n>0 && f->fila[pai(n)].chave > f->fila[n].chave){ //é menor e deve subir aux=f->fila[n];
f->fila[n]=f->fila[pai(n)]; f->index[f->fila[n].local]=n; f->fila[pai(n)]=aux; f->index[f->fila[pai(n)].local]=pai(n); up_heap(f, pai(n)); } } void insere_fila(p_fp FP, int i, int j){ //Heap de mínimo Item x; x.local=i; x.chave=j; FP->fila[FP->qtd]=x; FP->index[i]=FP->qtd; up_heap(FP,FP->qtd); FP->qtd++; }

//EXTRAINDO O MÍNIMO DA FILA DE PRIORIDADES

define esq(i) (2*i +1)

define dir(i) (2*i +2)

void desce_heap(p_fp f, int n){ int minf; Item aux; if(esq(n)<(f->qtd)){ //Existe filho esquerdo? minf=esq(n); //Existe e chutamos que ele é o menor.

    if(dir(n)<(f->qtd) //Existe filho direito?
    && f->fila[esq(n)].chave>f->fila[dir(n)].chave) //Se sim, ele é menor que o esquerdo?
        minf=dir(n); //O filho direito tem menor prioridade que o esquerdo

    if(f->fila[n].chave>f->fila[minf].chave){ //Temos o menor dos filhos. Ele é menor que o pai?
        aux=f->fila[n]; //Sim, trocamos ele com seu pai
        f->fila[n]=f->fila[minf];   f->index[f->fila[n].local]=n;
        f->fila[minf]=aux;          f->index[f->fila[minf].local]=minf;
        desce_heap(f, minf);
    }
}

}

Item min(p_fp f){ //Trocamos o item mínimo com o último Item aux=f->fila[0]; f->fila[0]=f->fila[(f->qtd)-1]; f->index[f->fila[0].local]=0; f->fila[(f->qtd)-1]=aux; f->index[f->fila[(f->qtd)-1].local]=(f->qtd)-1; f->qtd--; //Tiramos ele da qtd de itens desce_heap(f, 0); //Descemos na árvore return aux; //Retornamos o item mínimo }

//REMOVENDO ARESTAS DO GRAFO p_no remove_viz(p_no vizinhos, int vertice){ p_no prox; if(vizinhos==NULL){ return NULL; }else if(vizinhos->local!=vertice){ vizinhos->vizinho=remove_viz(vizinhos->vizinho,vertice); return vizinhos; }else{ //vizinhos->local==vertice, vamos remover prox=vizinhos->vizinho; free(vizinhos); return prox; } }

//DESTRUINDO GRAFO void libera_vizinhos(p_no lista){ if(lista!=NULL){ libera_vizinhos(lista->vizinho); free(lista); } } void destroi(p_grafo g){ int i; for(i=0; isz; i++) libera_vizinhos(g->mapa[i]); free(g->mapa); free(g); }

//FUNÇÃO QUE RETORNA PRIORIDADE int prioridade(p_fp f, int vertice){ int i,j; //Posição em fila que está o vértice i=f->index[vertice];

return f->fila[i].chave;

}

//ACHANDO CAMINHO MÍNIMO (DIJKSTRA)

define infinito 2147483647

int caminho_min(p_grafo g){ int i,pais=calloc((g->sz),sizeof(int)); //Conterá o caminho p_no j; //Auxiliar Item aux; //Auxiliar p_fp heap=criar_fila(g->sz); //Heap mínimo

for(i=0; i<g->sz; i++){
    pais[i]=-42; //Ninguém tem pai, a princípio
    insere_fila(heap, i, infinito); //Insiro todos os vértices no heap com peso infinito
}
pais[(g->sz)-1]=g->sz-1; //g->sz-1 é o RS, onde queremos chegar
heap->fila[heap->index[(g->sz)-1]].chave=0; //RS já é o RS, sua prioridade (chave) é zero

while(heap!=NULL){
    aux=min(heap); //Item mínimo do heap (caminho de menor distância)
    i=aux.local; //Vértice do item mínimo
    if(aux.chave!=infinito) //Ele não está a distância infinita, vai ser o próximo da franja
        for(j=g->mapa[i]; j!=NULL; j=j->vizinho) //Percorre os vizinhos na franja, i já parte da árvore
            if( (prioridade(heap,i)+j->tempo) < prioridade(heap,j->local) ){
            //Se sim, esse é o melhor caminho que eu conheço agora
                heap->fila[(heap->index[j->local])].chave=prioridade(heap,i)+j->tempo; //Diminuo a prioridade
                pais[j->local]=i; //Atualizo o pai
            }        
}
return pais;

}

int main(){ int n,m; p_grafo unicamp; int i,j,k,l,*caminho;

//Lendo entrada e formando grafo scanf("%d %d",&n,&m); unicamp=criar_grafo(n);

for(i=0; i<m; i++){ scanf("%d %d %d",&j,&k,&l); insere_aresta(unicamp,j,k,l); }

//Achando caminho mínimo caminho=malloc((unicamp->sz)*sizeof(int)); caminho=caminho_min(unicamp);

/*for(i=0;isz; i++) printf("%d\n",caminho[i]);

//Removendo arestas e encontrando o segundo caminho mínimo */ destroi(unicamp); return 0; }

[enoque]

Se a quantidade de elementos for 0 você faz o que? Aparentemente você não tá tratando isso, e caso não trate, vai acessar a posição -1 do vetor, e isso vai gerar um segmentation fault.

[eduarda-nicoletto]

Ah, sim!! Consertei! Fiz isso colocando no while mais uma condição, f->qtd!=0. No final, o vetor retornado pela função contém o caminho mínimo e alguns números aleatórios após ele. Tem como corrigir a função de forma que ela imprima apenas os números do caminho ou esse é o retorno esperado mesmo? @enoque @iagoac