Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
Nazgulled

Como usar uma min-heap no algoritmo de Dijkstra?

Recommended Posts

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á.

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.