# Algoritmo de Dijkstra
- Author: Luiz Schons
- Published: 2024-07-29
- URL: https://luizschons.com/pt-br/posts/algoritmo-dijkstra/
- English: https://luizschons.com/posts/dijkstras-algorithm.md
- Temas: Algoritmos
Edsger W. Dijkstra foi um cientista da computação holandês que fez contribuições significativas para a ciência da computação. Ele é mais conhecido por desenvolver o algoritmo de Dijkstra, que resolve o problema do caminho menos custoso em um grafo direcionado ou não direcionado com arestas não negativas.
Mas antes de falar sobre o algoritmo de Dijkstra, vamos falar sobre o algoritmo de `Pesquisa em Largura`.
### Pesquisa em Largura
Trabalhar com grafos é uma tarefa comum em computação. Um dos problemas mais comuns é encontrar o menor caminho entre dois vértices em um grafo. O algoritmo de `Pesquisa em Largura` mostra como encontrar o menor caminho em um grafo, como por exemplo, o caminho mais curto entre duas cidades em um mapa que tem cidades como vértices e estradas como arestas.
Imagine que precisamos sair de A para chegar em G. O algoritmo de `Pesquisa em Largura` nos ajuda a encontrar o menor caminho. O algoritmo começa visitando o vértice de origem (A) e então explora todos os vértices vizinhos. Depois disso, explora os vértices que estão a dois passos de distância e assim por diante.
No nosso caso o menor caminho é `A -> B -> E -> G`.
Nesse caso, temos somente 3 `passos` para chegar em G.
### Algoritmo de Dijkstra
Mas e se as arestas tiverem pesos? O algoritmo de `Pesquisa em Largura` não funciona mais. O algoritmo de Dijkstra é um algoritmo que encontra o caminho mais `barato` em um grafo direcionado ou não direcionado, com arestas que possuem pesos. O algoritmo de Dijkstra mantém duas listas: uma lista de vértices visitados e uma lista de vértices não visitados. Ele seleciona o vértice não visitado mais próximo do vértice de origem, marca-o como visitado e atualiza os pesos dos vértices vizinhos.
Vamos adaptar o exemplo anterior para incluir pesos nas arestas.
Agora temos pesos em cada aresta, e nosso desafio é encontrar o caminho em que a soma dos pesos seja menor.
Vamos aplicar o algoritmo de Dijkstra para encontrar o menor caminho de A para G.
- Começamos em A e olhamos os vizinhos dele: chegar em B custa 10 e chegar em C custa 5.
| Vértice | Distância de A | Caminho |
|---|
| A | 0 | A |
| B | 10 | A → B |
| C | 5 | A → C |
- O vértice não visitado mais próximo de A é C (5). Visitamos C e atualizamos os vizinhos dele: D passa a custar 7 (5 + 2) e F passa a custar 9 (5 + 4).
| Vértice | Distância de A | Caminho |
|---|
| A | 0 | A |
| B | 10 | A → B |
| C | 5 | A → C |
| D | 7 | A → C → D |
| F | 9 | A → C → F |
- O próximo mais próximo é D (7). Passando por D, E custa 8 (7 + 1). F custaria 13 (7 + 6), que é pior que 9, então F não muda.
| Vértice | Distância de A | Caminho |
|---|
| A | 0 | A |
| B | 10 | A → B |
| C | 5 | A → C |
| D | 7 | A → C → D |
| F | 9 | A → C → F |
| E | 8 | A → C → D → E |
- O próximo é E (8). Passando por E, G custa 10 (8 + 2). Visitar F e B depois não melhora nenhuma distância, então o algoritmo termina.
| Vértice | Distância de A | Caminho |
|---|
| A | 0 | A |
| B | 10 | A → B |
| C | 5 | A → C |
| D | 7 | A → C → D |
| F | 9 | A → C → F |
| E | 8 | A → C → D → E |
| G | 10 | A → C → D → E → G |
O menor caminho de A para G é `A -> C -> D -> E -> G`, com custo total 10.
### Aplicando isso com PHP
Vamos criar um exemplo prático em PHP para aplicar o algoritmo de Dijkstra.
```php
$graph = [
'A' => ['B' => 10, 'C' => 5],
'B' => ['E' => 8, 'D' => 3],
'C' => ['D' => 2, 'F' => 4],
'D' => ['E' => 1, 'F' => 6],
'E' => ['G' => 2],
'F' => ['E' => 1],
'G' => []
];
function dijkstra(array $graph, string $source, string $target): array
{
$dist = array_fill_keys(array_keys($graph), INF);
$prev = array_fill_keys(array_keys($graph), null);
$dist[$source] = 0;
// SplPriorityQueue devolve primeiro a maior prioridade,
// então usamos a distância negativa para pegar o vértice mais próximo.
$queue = new SplPriorityQueue();
$queue->insert($source, 0);
while (!$queue->isEmpty()) {
$u = $queue->extract();
foreach ($graph[$u] as $v => $cost) {
$alt = $dist[$u] + $cost;
if ($alt < $dist[$v]) {
$dist[$v] = $alt;
$prev[$v] = $u;
$queue->insert($v, -$alt);
}
}
}
$path = [];
for ($u = $target; $u !== null; $u = $prev[$u]) {
array_unshift($path, $u);
}
return $path;
}
$path = dijkstra($graph, 'A', 'G');
echo implode(' -> ', $path); // A -> C -> D -> E -> G
```
Segue o passo a passo da execução do algoritmo:
- Inicializamos as distâncias e a fila de prioridade.
- Inicializamos a distância do vértice de origem como 0.
- Enquanto a fila de prioridade não estiver vazia, extraímos o vértice com a menor distância.
- Para cada vértice vizinho, calculamos a distância alternativa e atualizamos a distância se for menor.
- Construímos o caminho percorrendo os vértices anteriores.
- Retornamos o caminho.
## Conclusão
Com o aumento do uso de IA, Machine Learning e Big Data, o conceito de grafos se tornou cada vez mais importante. O algoritmo de Dijkstra é um dos algoritmos mais importantes para encontrar o menor caminho em um grafo. Espero que você tenha entendido como o algoritmo de Dijkstra funciona e como ele pode ser aplicado em um cenário do mundo real. Se você gostou desse artigo, deixe um comentário e compartilhe com seus amigos. Até a próxima!