Algoritmo de Dijkstra

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.

1. 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

2. 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

3. 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

4. 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.

$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:

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 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!