Algoritmo de caminho de custo mínimo de Dijkstra - uma introdução detalhada e visual

Artigo original: https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/

Boas-vindas! Se você sempre quis aprender e entender o algoritmo de Dijkstra, este artigo é para você. Você verá como ele funciona nos bastidores com uma explicação gráfica passo a passo.

Você aprenderá:

• Conceitos básicos sobre grafos (uma breve revisão).
• Para que o algoritmo de Dijkstra é utilizado.
• Como o algoritmo funciona através de um exemplo passo a passo.

Vamos começar. ✨

🔹 Introdução aos grafos

Vamos começar com uma breve introdução aos grafos.

Conceitos básicos

Grafos são estruturas de dados usadas para representar "conexões" entre pares de elementos.

• Esses elementos são chamados de nós (ou vértices). Eles representam objetos, pessoas ou entidades da vida real.
• As conexões entre os nós são chamadas de arestas.

Esta é uma representação gráfica de um grafo:

Os nós são representados por círculos coloridos e as arestas são representadas por linhas que conectam esses círculos.

💡 Dica: dois nós estarão conectados se houver uma aresta entre eles.

Aplicações

Os grafos são diretamente aplicáveis a cenários do mundo real. Por exemplo, poderíamos usá-los para modelar uma rede de transporte, onde os nós representariam instalações que enviam ou recebem produtos e arestas representariam estradas ou caminhos que os conectam (veja abaixo).

Tipos de grafos

Os grafos podem ser:

• Não dirigidos: se para cada par de nós conectados, você pode ir de um nó para o outro em ambas as direções.
• Dirigidos: se para cada par de nós conectados, você só pode ir de um nó para outro em uma direção específica. Usamos setas em vez de linhas simples para representar arestas dirigidas.

💡 Dica: neste artigo, abordaremos grafos não dirigidos.

Grafos ponderados

Um grafo ponderado é um grafo cujas arestas têm um "peso" ou "custo". O peso de uma aresta pode representar distância, tempo ou qualquer coisa que modele a "conexão" entre o par de nós que ela conecta.

Por exemplo, no grafo ponderado abaixo, você pode ver um número em azul próximo de cada aresta. Este número é usado para representar o peso da aresta correspondente.

💡 Dica: esses pesos são essenciais para o Algoritmo de Dijkstra. Você verá por que a seguir.

🔸 Introdução ao algoritmo de Dijkstra

Agora que você conhece os conceitos básicos de grafos, vamos nos aprofundar nesse algoritmo incrível.

• Propósito e casos de uso
• História
• Elementos básicos do algoritmo
• Requisitos

Propósito e casos de uso

Com o algoritmo de Dijkstra, você poderá encontrar o caminho de menor custo entre nós em um grafo. Particularmente, você poderá encontrar o caminho de menor custo entre um nó (denominado “origem”) e todos os outros nós do grafo, produzindo uma árvore de custo-mínimo.

Este algoritmo é usado em dispositivos GPS para encontrar o caminho mais curto entre a localização atual e o destino. Ele possui ampla aplicação na indústria, principalmente em domínios que requerem modelagem de redes

História

Este algoritmo foi criado e publicado pelo Dr. Edsger W. Dijkstra, um brilhante cientista da computação e engenheiro de software holandês.

Em 1959, ele publicou um artigo de 3 páginas intitulado "A note on two problems in connexion with graphs" (Uma nota sobre dois problemas em conexão com grafos, em tradução livre), onde explicou seu novo algoritmo.

Durante uma entrevista em 2001, o dr. Dijkstra revelou como e por que desenvolveu o algoritmo:

Qual é o caminho mais curto para viajar de Roterdã a Groningen? É o algoritmo para o caminho mais curto, que projetei em aproximadamente 20 minutos. Certa manhã, eu estava fazendo compras em Amsterdã com minha noiva e, cansado, sentamos no terraço do café para beber uma xícara de café e eu estava pensando se poderia fazer isso, e então, desenvolvi o algoritmo para o caminho mais curto . Como eu disse, foi uma invenção de 20 minutos. Na verdade, foi publicado em 1959, três anos depois. A publicação continua bem legal. Uma das razões por que ela é tão legal foi que eu a desenhei sem lápis e papel. Sem lápis e papel, você é quase forçado a evitar todas as complexidades evitáveis. Eventualmente, esse algoritmo se tornou, para minha grande surpresa, um dos pilares da minha fama. — Conforme citado no artigo Edsger W. Dijkstra em An interview with Edsger W. Dijkstra (Uma entrevista com Edsger W. Dijkstra).

⭐ Inacreditável, não? Em apenas 20 minutos, o Dr. Dijkstra desenvolveu um dos algoritmos mais famosos da história da Ciência da Computação.

Noções básicas do algoritmo de Dijkstra

• O Algoritmo de Dijkstra basicamente começa no nó que você escolhe (o nó de origem) e analisa o grafo para encontrar o caminho de menor custo entre esse nó e todos os outros nós do grafo.
• O algoritmo mantém o registro da distância mais curta atualmente conhecida de cada nó até o nó de origem e atualiza esses valores se encontrar um caminho de menor custo.
• Uma vez que o algoritmo encontrou o caminho de menor custo entre o nó de origem e outro nó, esse nó é marcado como "visitado" e adicionado ao caminho.
• O processo continua até que todos os nós do grafo tenham sido adicionados ao caminho. Desta forma, temos um caminho que conecta o nó de origem a todos os outros nós seguindo o caminho de menor custo possível para chegar a cada nó.

Requisitos

O Algoritmo de Dijkstra só funciona com grafos com pesos positivos. Isso porque, durante o processo, os pesos das arestas devem ser somados para encontrar o caminho de menor custo.

Se houver um peso negativo no grafo, o algoritmo não funcionará corretamente. Uma vez que um nó tenha sido marcado como "visitado", o caminho atual para esse nó é marcado como o caminho de menor custo para chegar a esse nó. E pesos negativos podem alterar isso se o peso total puder ser decrementado após essa etapa ter ocorrido.

🔹 Exemplo do algoritmo de Dijkstra

Agora que você sabe mais sobre esse algoritmo, vamos ver como ele funciona nos bastidores com um exemplo passo a passo.

Temos este grafo:

O algoritmo gerará o caminho de menor custo (neste caso, o caminho mais curto) do nó 0 para todos os outros nós do grafo.

💡 Dica: neste caso, assumiremos que o peso das arestas representa a distância entre dois nós.

Teremos o caminho mais curto do nó 0 ao nó 1, do nó 0 ao nó 2, do nó 0 ao nó 3, e assim por diante para cada nó do grafo.

Inicialmente, temos esta lista de distâncias (veja a lista abaixo):

• A distância do nó de origem até ele mesmo é 0. Para este exemplo, o nó de origem será o nó 0, mas pode ser qualquer nó que você escolher.
• A distância do nó de origem para todos os outros nós ainda não foi determinada, então usamos o símbolo do infinito para representar isso inicialmente.

Também temos esta lista (veja abaixo) para acompanhar os nós que ainda não foram visitados (nós que não foram incluídos no caminho):

💡 Dica: lembre-se de que o algoritmo é concluído quando todos os nós forem adicionados ao caminho.

Como estamos escolhendo começar no nó 0, podemos marcar esse nó como visitado. De forma equivalente, nós o cortamos da lista de nós não visitados e adicionamos uma borda vermelha ao nó correspondente no diagrama:

Agora precisamos verificar a distância do nó 0 até seus nós adjacentes. Como você pode ver, estes são os nós  1 e 2 (veja as bordas vermelhas):

💡 Dica: isso não significa que estamos adicionando imediatamente os dois nós adjacentes ao caminho mais curto. Antes de adicionar um nó a este caminho, precisamos verificar se encontramos o caminho mais curto para alcançá-lo. Estamos simplesmente fazendo um processo de exame inicial para ver as opções disponíveis.

Precisamos atualizar as distâncias do nó 0 ao 1 e ao nó 2 com os pesos das arestas que os conectam ao nó 0 (origem). Estes pesos são 2 e 6, respectivamente:

Após atualizar as distâncias dos nós adjacentes, precisamos:

• Selecionar o nó mais próximo do nó de origem com base nas distâncias conhecidas atuais.
• Marcá-lo como visitado.
• Adicioná-lo ao caminho.

Se verificarmos a lista de distâncias, podemos ver que o nó 1 tem a menor distância até a origem (distância igual a 2), então, nós o adicionamos ao caminho.

No diagrama, podemos representar isso com uma aresta vermelha:

Marcamos com um quadrado vermelho na lista para representar que foi "visitado" e que encontramos o caminho mais curto para este nó:

Riscamos da lista de nós não visitados:

Agora, precisamos analisar os novos nós adjacentes para encontrar o caminho mais curto para alcançá-los. Analisaremos apenas os nós que são adjacentes aos nós que já fazem parte do caminho mais curto (o caminho marcado com arestas vermelhas).

Os nós 3 e 2 são ambos adjacentes aos nós que já estão no caminho porque estão diretamente conectados aos nós1 e 0, respectivamente, como você pode ver abaixo. Esses são os nós que analisaremos na próxima etapa.

Como já temos a distância do nó de origem ao nó 2 anotado em nossa lista, não precisamos atualizar a distância desta vez. Precisamos apenas atualizar a distância do nó de origem ao novo nó adjacente (o nó 3):

Essa distância é igual a 7. Vamos ver o porquê.

Para encontrar a distância do nó de origem para outro nó (neste caso, nó 3), somamos os pesos de todas as arestas que formam o caminho mais curto para chegar a esse nó:

• No caso do nó 3: a distância total é 7 porque adicionamos os pesos das arestas que formam o caminho0 -> 1 -> 3 (2  para a aresta 0 -> 1 e 5 para a aresta 1 -> 3).

Agora que temos a distância até os nós adjacentes, temos que escolher qual nó será adicionado ao caminho. Devemos selecionar o nó não visitado com a distância mais curta (atualmente conhecida) até o nó de origem.

A partir da lista de distâncias, podemos detectar imediatamente que este é um nó 2 cuja distância é 6:

Adicionamos ao caminho graficamente com uma borda vermelha ao redor do nó e uma aresta vermelha:

Também o marcamos como visitado adicionando um pequeno quadrado vermelho na lista de distâncias e riscando-o da lista de nós não visitados:

Agora precisamos repetir o processo para encontrar o caminho mais curto do nó de origem até o novo nó adjacente, que é o nó 3.

Você pode ver que temos dois caminhos possíveis 0 -> 1 -> 3 ou 0 -> 2 -> 3. Vamos ver como podemos decidir qual é o caminho mais curto.

O nó 3 já possui uma distância na lista que foi registrada anteriormente (7, veja a lista abaixo). Essa distância foi resultado de um passo anterior, onde somamos os pesos 5 e 2 das duas arestas que precisávamos cruzar para seguir o caminho 0 -> 1 -> 3.

Mas agora temos outra alternativa. Se escolhermos seguir o caminho0 -> 2 -> 3, precisaríamos seguir duas arestas 0 -> 2 e 2 -> 3 com pesos 6 e 8, respectivamente, o que representa uma distância total igual a 14.

Claramente, a primeira distância (existente) é menor (7 x 14), então escolheremos manter o caminho original 0 -> 1 -> 3. Só atualizamos a distância se o novo caminho for mais curto.

Portanto, adicionamos este nó ao caminho usando a primeira alternativa: 0 -> 1 -> 3.

Marcamos este nó como visitado e o riscamos da lista de nós não visitados:

Agora, repetimos esse processo.

Precisamos verificar os novos nós adjacentes que não visitamos até agora. Desta vez, esses nós são os nós 4 e 5, já que ambos são adjacentes ao nó 3.

Atualizamos as distâncias desses nós até o nó de origem, sempre tentando encontrar um caminho mais curto, se possível:

• No caso do nó 4: a distância é 17 para o caminho  0 -> 1 -> 3 -> 4.
• No caso do nó 5: a distância é 22 para o caminho 0 -> 1 -> 3 -> 5.

💡 Dica: Observe que só podemos considerar estender o caminho mais curto (marcado em vermelho). Não podemos considerar caminhos que nos levarão através de arestas que não foram adicionadas ao caminho mais curto (por exemplo, não podemos formar um caminho que passe pela aresta2 -> 3).

Precisamos escolher qual nó não visitado será marcado como visitado. Neste caso, é o nó 4 porque tem a distância mais curta na lista de distâncias. Adicionamos graficamente no diagrama:

Também o marcamos como "visitado" adicionando um pequeno quadrado vermelho na lista:

E o riscamos da lista de nós não visitados:

E repetimos o processo novamente. Verificamos os nós adjacentes: nós 5 e 6. Precisamos analisar cada caminho possível que podemos seguir para alcançá-los a partir de nós que já foram marcados como visitados e adicionados ao caminho.

No caso do nó 5:

• A primeira opção é seguir o caminho 0 -> 1 -> 3 -> 5, que tem uma distância de 22 para o nó de origem (2 + 5 + 15). Essa distância já foi registrada na lista de distâncias em uma etapa anterior.
• A segunda opção seria seguir o caminho 0 -> 1 -> 3 -> 4 -> 5, que tem uma distância de 23 para o nó de origem (2 + 5 + 10 + 6).

Claramente, o primeiro caminho é mais curto, então o escolhemos para nó 5.

No caso do nó 6:

• O caminho disponível é 0 -> 1 -> 3 -> 4 -> 6, que tem uma distância de 19 para o nó de origem (2 + 5 + 10 + 2).

Marcamos o nó com a distância mais curta (atualmente conhecida) como visitada. Neste caso, o nó6.

E o riscamos da lista de nós não visitados:

Agora temos este caminho (marcado em vermelho):

Apenas um nó ainda não foi visitado, o nó 5. Vamos ver como podemos incluí-lo no caminho.

Existem três caminhos diferentes que podemos seguir para alcançar o nó 5a partir dos nós que foram adicionados ao caminho:

• Opção 1: 0 -> 1 -> 3 -> 5 com uma distância de 22 (2 + 5 + 15).
• Opção 2: 0 -> 1 -> 3 -> 4 -> 5 com uma distância de 23 (2 + 5 + 10 + 6).
• Opção 3: 0 -> 1 -> 3 -> 4 -> 6 -> 5 com uma distância de 25 (2 + 5 + 10 + 2 + 6).

Selecionamos o caminho: 0 -> 1 -> 3 -> 5 com uma distância de 22.

Marcamos o nó como visitado e o riscamos da lista de nós não visitados:

E aí está! Temos o resultado final com o caminho mais curto do nó 0 até cada nó do grafo.

No diagrama, as linhas vermelhas marcam as arestas que pertencem ao caminho mais curto. Você precisa seguir essas arestas para seguir o caminho mais curto para chegar a um determinado nó no grafo a partir do nó 0.

Por exemplo, se você deseja alcançar o nó 6 a partir do nó 0, basta seguir as arestas vermelhas e estará, automaticamente, seguindo o caminho mais curto 0 -> 1 -> 3 -> 4 - > 6.

🔸 Resumindo

• Os grafos são usados para modelar conexões entre objetos, pessoas ou entidades. Eles têm dois elementos principais: nós e arestas. Os nós representam objetos e as arestas representam as conexões entre esses objetos.
• O algoritmo de Dijkstra encontra o caminho mais curto entre um determinado nó (que é chamado de "nó de origem") e todos os outros nós em um grafo.
• Este algoritmo usa os pesos das arestas para encontrar o caminho que minimiza a distância total (peso) entre o nó de origem e todos os outros nós.

Eu realmente espero que você tenha gostado do artigo e o tenha achado útil. Agora, você sabe como o algoritmo de Dijkstra funciona nos bastidores. Siga a autora no Twitter (@EstefaniaCassN) e confira os cursos da autora on-line.