[pt-br] Algoritmo Dijkstras

[ananeridev]

Dado um gráfico e um vértice de origem no gráfico, encontre os caminhos mais curtos da origem para todos os vértices no gráfico fornecido.
O algoritmo de Dijkstra é muito semelhante ao algoritmo de Prim para uma árvore de abrangência mínima. Como o MST de Prim, geramos um SPT (árvore de caminho mais curto) com a origem especificada como raiz. Mantemos dois conjuntos, um conjunto contém vértices incluídos na árvore do caminho mais curto, outro conjunto inclui vértices ainda não incluídos na árvore do caminho mais curto. Em cada etapa do algoritmo, encontramos um vértice que está no outro conjunto (conjunto ainda não incluído) e que possui uma distância mínima da fonte.

Abaixo estão as etapas detalhadas usadas no algoritmo de Dijkstra para encontrar o caminho mais curto de um único vértice de origem até todos os outros vértices no gráfico fornecido.

Algoritmo

1. Crie um conjunto sptSet (conjunto da árvore do caminho mais curto) que rastreie os vértices incluídos na árvore do caminho mais curto, ou seja, cuja distância mínima da origem seja calculada e finalizada. Inicialmente, este conjunto está vazio.
2. Atribua um valor de distância a todos os vértices no gráfico de entrada. Inicialize todos os valores de distância como INFINITE. Atribua o valor da distância como 0 ao vértice de origem, para que seja escolhido primeiro.
3. Embora o sptSet não inclua todos os vértices
   … .A) Escolha um vértice u que não esteja no sptSet e tenha um valor mínimo de distância.
   … .B) Inclua u no sptSet.
   … .C) Atualize o valor da distância de todos os vértices adjacentes de u. Para atualizar os valores da distância, itere através de todos os vértices adjacentes. Para cada vértice adjacente v, se a soma do valor da distância de u (da fonte) e o peso da aresta u-v for menor que o valor da distância de v, atualize o valor da distância de v.

Vamos entender com a imagem de exemplo abaixo

O conjunto sptSet está inicialmente vazio e as distâncias atribuídas aos vértices são {0, INF, INF, INF, INF, INF, INF, INF, INF} em que INF indica infinito. Agora escolha o vértice com o valor mínimo de distância. O vértice 0 é escolhido, inclua-o no sptSet. Então sptSet se torna {0}. Depois de incluir 0 no sptSet, atualize os valores de distância de seus vértices adjacentes. Os vértices adjacentes de 0 são 1 e 7. Os valores de distância de 1 e 7 são atualizados como 4 e 8. O subgráfico a seguir mostra vértices e seus valores de distância, apenas os vértices com valores de distância finita são mostrados. Os vértices incluídos no SPT são mostrados na cor verde.

Pick the vertex with minimum distance value and not already included in SPT (not in sptSET). The vertex 1 is picked and added to sptSet. So sptSet now becomes {0, 1}. Update the distance values of adjacent vertices of 1. The distance value of vertex 2 becomes 12.

Escolha o vértice com o valor da distância mínima e ainda não esteja incluído no SPT (não no sptSET). O vértice 7 é escolhido. Então, o sptSet agora se torna {0, 1, 7}. Atualize os valores da distância dos vértices adjacentes de 7. O valor da distância do vértice 6 e 8 torna-se finito (15 e 9, respectivamente).

Escolha o vértice com o valor da distância mínima e ainda não esteja incluído no SPT (não no sptSET). O vértice 6 é escolhido. Então, o sptSet agora se torna {0, 1, 7, 6}. Atualize os valores da distância dos vértices adjacentes de 6. Os valores da distância dos vértices 5 e 8 são atualizados.

Repetimos as etapas acima até que o sptSet inclua todos os vértices do gráfico fornecido. Finalmente, obtemos a seguinte Árvore de caminho mais curto (SPT).

TIP
Você pode uma uma matriz booleana sptSet [] para representar o conjunto de vértices incluídos no SPT. E se um valor sptSet [v] for verdadeiro, o vértice v será incluído no SPT, caso contrário não. A matriz dist [] é usada para armazenar os menores valores de distância de todos os vértices.

Qualquer dúvida entre no slack da womakerscode e vamos discutir a solução! Eu resolvi com Java!

Vídeo com explicação e resolução, ta em inglês: https://www.youtube.com/watch?v=_lHSawdgXpI