Nesse trabalho da disciplina Teoria dos Grafos, o grupo precisa escolher um dataset específico (no nosso caso, um grafo ponderado armazenado no arquivo football.gml) e implementar o algoritmo de Dijkstra para extrair uma árvore de caminhos mínimos de G.

Ao decorrer da explicação desse trabalho, ficará clara sua semelhança com o T3: Árvores geradoras mínimas e comunidades, já implementado pelo grupo e disponível em: Árvores geradoras mínimas e comunidades

Uma Árvore de Caminhos Ótimos em relação a um vértice s é uma árvore que possui os menores custos saindo de s e indo para todos os demais vértices de G, o trabalho pede para que usemos o algoritmo  Djikstra para encontrar essa árvore, então vamos explicar os conceitos desse algoritmo:

Muito parecido com o funcionamento do algoritmo de Prim, Djikstra tem uma diferença no critério de adição à aresta de menor peso. Ele compara  λ(v) >  λ(u) + w(u, v), ou seja, o critério de escolha da aresta é o peso da aresta mais o peso atual do caminho já percorrido e não apenas o peso da aresta (como no de Prim).

pseudo_d

Essa é a implementação comentada do algoritmo de Dijkstra em Python usando as bibliotecas NetworkX e NumPy.

djessica_1

djessica_2

 

 

Uma forma de fazer 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).

No trecho de código a seguir, atribuímos 2 a K

djessica_5

O resultado obtido foi:

djessica_6

E o seguinte Grafo:

2

No caso de atribuição 3 a K:

djessica_3

Resultado:

djessica_7

Grafo:

3

Como podemos ver, o tamanho dos grupos manteve-se semelhante.

O código fonte e demais arquivos usados nesse trabalho estão disponíveis em: https://github.com/WellitonAlt/Grafos

 

Referências:

Notas de aula da disciplina.

 

Advertisements