Algoritmo Djikstra

Esse tutorial tem como objetivo passar uma noção do algoritmo de Dijkstra e também algumas observações a serem feitas. Ele sempre encontra o melhor caminho e é muito parecido com um algoritmo já visto no blog, o algoritmo de Prim.
A diferença entre o de Prim e Dijkstra é a operação de relaxamento nas arestas (primitiva relax), que verifica se é possível diminuir o custo do caminho até o vértice. O Algoritmo de Djikstra soluciona o problema do caminho mais curto num dado grafo. Iniciando em um vértice raiz, logo esse tem custo 0, olhando agora para as adjacências ele escolhe aquelas que tiverem menor custo para atingir o vértice, ou seja, é necessário olhar para um custo já calculado + peso da aresta (onde difere de Prim) e comparar com o custo existente no vértice que deseja chegar. Para isso utilizamos de algumas primitivas que são a relax e extractMin.

Lembrando que antes era necessário ler de um arquivo específico os nossos dados, que foi feito nesta parte do código:

Agora que já temos o nosso grafo e também as nossas primitivas que são usadas no algoritmo, implementamos ele:

Note o uso das primitivas nas linhas 70 e 76.
O seu segundo argumento S, é usado para nosso K (vértices que terão custo 0 inicialmente) e veremos mais a frente o porque isso foi usado.
Agora quando esse algoritmo foi executado no nosso grafo, obtivemos este resultado:

Este grafo acima foi usado um conjunto K = 1, ou seja, apenas o vértice raiz tinha custo como 0. Isso implica que no grafo existirá apenas um grupo de vértices, se mudarmos esse valor teremos novos resultados. A seguir aplicamos K = 2 e K = 3 respectivamente a fim de observar o que aconteceria no crescimento do grafo.

Os vértices com custo 0 nesse grafo a cima foram os vértices 29 e 102. É possível observar no grafo que eles fazem partes de comunidades diferentes. Como aqui o K=2 temos 2 grupos distintos de vértices, chamamos de comunidade.
Já na figura abaixo temos K=3 com os vértices que iniciaram seu custo em zero sendo 64, 88 e 125.

Fontes e ferramentas:

https://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra;

https://passeiemgrafos.wordpress.com/;

Notas de aula da matéria;

Python(x,y);

Spyder Python.