Algoritmo de Dijkstra
O que o algoritmo faz é criar uma fila de prioridades para organizar os vértices de modo que quanto menor o custo maior a prioridade do vértice em questão. Assim, a ideia é expandir primeiramente os menores ramos da árvore de caminhos mínimos, na expectativa de que os caminhos mínimos mais longos usarão como base os subcaminhos obtidos anteriormente.
Metodologia
Após a implementação do algoritmo, uma forma de crescer várias subárvores de caminhos mínimos é inicializar várias "sources", ou seja, atribuir custo inicial zero a um número K de vértices. O restante do algoritmo permanece intacto. O que irá acontecer é um processo de disputa entre cada uma das raízes para verificar qual delas irá conquistar cada vértice de G. Ao final da execução um vértice estará "pendurado" apenas a uma única subárvore, fazendo com que tenhamos vários grupos de nós, similar ao que acontecia com as MST's. Porém aqui há supervisão no processo de formação dos grupos, uma vez que o usuário pode definir de onde as subárvores irão iniciar o crescimento (esses pontos devem ser escolhidos de forma a definir o centro dos agrupamentos).
Questionamentos
Considerando o grafo abaixo, mostre os resultados (plote graficamente) obtidos para:
 |
| Grafo com 59 cidades da Alemanha ocidental |
Através do algoritmo de Dijkstra em Python, as bibliotecas NumPy, NetworkX e Matplolib foi possível plotar os grafos.
 |
| Algoritmo de Dijkstra em Python |
 |
| Plotando os grafos com agrupamento K=2 e K=3 |
Resultados
a) 2 agrupamentos (K = 2)
Pegando os vértices 0 e 42
b) 3 agrupamentos (K = 3)
Pegando os vértices 0, 26 e 53
Nenhum comentário:
Postar um comentário