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 visitamos todos os vértices vizinhos.
2. O próximo vértice mais próximo de A é C. Então visitamos C e atualizamos as distâncias dos vértices vizinhos.
3. O próximo vértice mais próximo de A é D. Então visitamos D e atualizamos as distâncias dos vértices vizinhos.
4. O próximo vértice mais próximo de A é E. Então visitamos E e atualizamos as distâncias dos vértices vizinhos.
O menor caminho de A para G é A -> C -> D -> E -> G.
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' => 2, 'F' => 6],
'E' => ['G' => 2],
'F' => ['E' => 1],
'G' => []
];
function dijkstra($graph, $source, $target)
{
$dist = [];
$prev = [];
$queue = new SplPriorityQueue();
foreach ($graph as $vertex => $adj) {
$dist[$vertex] = INF;
$prev[$vertex] = null;
$queue->insert($vertex, $vertex === $source ? 0 : INF);
}
$dist[$source] = 0;
while (!$queue->isEmpty()) {
$u = $queue->extract();
if (!empty($graph[$u])) {
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 = [];
$u = $target;
while (isset($prev[$u])) {
array_unshift($path, $u);
$u = $prev[$u];
}
array_unshift($path, $source);
return $path;
}
$path = dijkstra($graph, 'A', 'G');
echo implode(' -> ', $path);
Segue o passo a passo da execução do algoritmo:
1. Inicializamos as distâncias e a fila de prioridade.
2. Inicializamos a distância do vértice de origem como 0.
3. Enquanto a fila de prioridade não estiver vazia, extraímos o vértice com a menor distância.
4. Para cada vértice vizinho, calculamos a distância alternativa e atualizamos a distância se for menor.
5. Construímos o caminho percorrendo os vértices anteriores. 6. Retornamos o caminho.
Conclusão
Com o aumento do uso de AI, 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!
