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

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