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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586193682/83906eab-e030-4187-ada0-a6fb599c5a92.png align="left")

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586196340/21335b16-46e7-41d0-83ce-9616afcbc13c.png align="left")

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.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586198835/e98599cc-e8c7-42f7-90fd-db6bc0585fe0.png align="left")

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.
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586200913/c8fb16dd-c96c-46f1-9631-8cc994f9e8c8.png align="left")

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.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586202833/605433b6-8e50-4537-a177-c1622ea93383.png align="left")

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.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586204480/9501673c-afae-4064-8bbc-07d604383605.png align="left")

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.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586206680/0b1d5fc0-12a1-45e9-9da0-d87c7527efa4.png align="left")

O menor caminho de A para G é `A -> C -> D -> E -> G`.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1728586209257/72e9e802-5834-479a-856d-0a9cb6649c96.png align="left")

### Aplicando isso com PHP

Vamos criar um exemplo prático em PHP para aplicar o algoritmo de Dijkstra.

```php
<?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!