Na applet abaixo é utilizado o algoritmo de Dijkstra para
calcular Caminhos mais curtos de única origem.
Existem três opções:
Binário: utiliza o heap binário mínimo.
Vetor W: utiliza um vetor de VW posições como
heap mínimo. Cada posição i
corresponde a cabeça de uma lista encadeada com todos os cuja
chave seja i. A complexidade deste algoritmo é
O(WV+E) conforme solicitado no exercício 24.3-6 de [CORMEN].
Misto: utiliza um heap binário mínimo
onde cada elemento do heap é a cabeça de uma lista
encadeada de elementos de mesma chave. Além disto existe um vetor
de VW posições, onde cada elemento i
indica a posição da lista de chave i no
heap binário. Este vetor auxiliar serve para auxiliar
operações de decremento de chave. A complexidade deste
algoritmo é O((V+E) lgW) conforme solicitado no exercício
24.3-7 de [CORMEN].
Instruções de uso da applet:
Para inserir um novo grafo primeiro digite o número de vértices
no respectivo campo e clique no botão "Criar grafo vazio".
A tabela representa uma lista de adjacências com ponderação.
Cada linha pertence a um vértice e cada coluna pertence às
arestas que se originam daquele vértice.
As arestas são separadas por ponto-e-vírgula. Para cada
aresta é necessário informar o vértice destino e o
seu peso (separados por vírgula).
Os três botões: "Binário", "Vetor
W" e "Misto" disparam respectivamente as três versões
do algoritmo de Dijkstra com heaps diferentes.
A tabela abaixo dos botões arpesenta o grafo resultante.
No início da applet é apresentado um grafo exemplo.
Detalhes de implementação
Para quem pretende analisar a implementação dos
algoritmos, as seguintes classes são as mais relevantes:
Pacote graph:
Vertex: representa um vértice e sua lista de
arestas.
Edge: representa uma aresta ponderada.
Graph: representa um grafo completo na forma de lista de
adjacências.
TableGraph: componente gráfico que apresenta grafo
visualmente (na forma de tabela) e permite sua modificação.
Pacote graph.spath:
Dijkstra: representa o algoritmo de Dijkstra independente
da implementação de heap. O heap é
passado como parâmetro e pode possuir qualquer implementação,
contanto que siga uma interface padrão de acesso.
Pacote heap:
MinimumHeap: interface padrão para heap mínimo
(usada por Dijkstra).
BinaryHeap: heap binário (nada mais óbvio!).
WHeap: heap implementado com o vetor VW.
WBinaryHeap: heap misto (binário e vetor VW).
[CORMEN] Cormen, Thomas H. et. al. Algoritmos: teoria e prática -
tradução da 2a edição americana. Rio de
Janeiro: Campus, 2002.