Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Nazgulled

Como usar uma min-heap no algoritmo de Dijkstra?

Mensagens Recomendadas

Nazgulled

Boas,

Preciso de uma ajudinha dos gurus em algoritmos do fórum porque isto não é propriamente onde a minha sabedoria está concentrada (se é que está em algum lado).

De momento estou a usar este código para calcular o caminho mais curto num grafo entre dois vértices.

Pelo que tenho lido, o uso de uma min-heap reduz consideravelmente o tempo de execução do mesmo para grafos muito grandes. Mas como é que a uso? Onde é que insiro elementos na heap? Onde é que removo? Onde é que extraio o mínimo? Etc...

E já agora, visto que ainda não desenvolvi a min-heap, quais são as operações mínimas necessárias para usar isto no Dijkstra? O resto não me interessa para já.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
DVD

Geralmente o min-heap é constituido por:

- buildHeap (array, length) -> pega num array e constroi um heao

- heapify(heap,p,length) -> que dado um p (que é um elemento do heap) mantem a propriedade de heap(max ou min)

- add(heap, value) -> adiciona ao heap o value.

Nunca usei o algoritmo de Dijkstra mas pelo que li, usaria conjuntos disjuntos para o resolver ao invés do min-heap

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pedrosorio

Isso só responde à parte secundária da minha pergunta... :/

http://en.wikipedia.org/wiki/Binary_heap

Para o caso do Dijkstra podes implementar a heap num array (de forma a representar uma árvore binária de forma compacta) como está explicado em "Heap implementation" já que nunca precisas de aumentar o tamanho da heap.

Eu diria que a forma mais simples de implementar a heap para Dijkstra é ter em cada posição do array (chamemos-lhe A) o nó do grafo (0,1,2...) , e ter um outro array que contenha para cada nó do grafo a sua distância ao nó origem (chamemos-lhe D). Para além disso precisas de guardar um inteiro que te diga quantos nós é que ainda tens na heap (i.e. no conjunto Q do Dijkstra).

Se assim for, só precisas de inicializar um array com o número de nós do grafo que contenha o nó origem na posição 0 e os restantes nas outras (se o nó origem fosse o 6 e tivesses 10 nós no grafo ficaria um array deste estilo: A = {6,0,1,2,3,4,5,7,8,9}), que sendo assim, respeita a propriedade de heap.

Depois, só precisas de olhar para o nó que está na posição 0 da heap, processá-lo e aos nós adjacentes como fazes normalmente em Dijkstra, e em seguida aplicar a operação que te restabelece a propriedade de heap (porque agora tens uma série de nós que não estão organizados pela distância).

Para fazer isto, tens que diminuir o inteiro que te diz quantos nós tens na heap (i.e. retirar o nó que processaste), e colocar o último nó na primeira posição, ficando, no exemplo, assim: {9,0,1,2,3,4,5,7,8,9}  (o último 9 não tem importância já que a tua heap só tem 9 elementos, agora). Agora aplicas o algoritmo de Build-Max-Heap que depende do Max-Heapify (implementas cada um destes mas nas suas versões min) que estão na wikipedia, para que a estrutura volte a ser uma heap.

Como estás a guardar na heap os números dos nós e não as distâncias, onde aparece A[ right ] > A[ largest ], por exemplo, deves de facto ter D[ A[ right ] ] > D[ A[ largest ] ]. (Atenção: no caso da min-heap é exactamente o oposto, i.e. menor em vez de maior).


Não respondo a dúvidas por mensagem.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.