Estruturas de dados · Menor caminho ponderado

Não queremos menos passos. Queremos menor custo.

Dijkstra mantém a melhor distância conhecida até cada vértice e sempre escolhe, entre os candidatos, aquele com o menor custo acumulado.

Dijkstra Fila de prioridade Relaxamento priority_queue Pesos não negativos

Qual problema vamos resolver?

Usando o mesmo grafo da aula anterior, queremos sair de A e chegar em G pagando o menor custo possível.

Origem

A

A distância de A para ele mesmo começa em 0.

Destino

G

Queremos descobrir o menor custo acumulado até G.

Pesos

Diferentes

Cada aresta possui seu próprio custo.

A ideia do Dijkstra

O algoritmo repete três ideias simples:

Pegue o menor custo disponível

→

Examine seus vizinhos

→

Tente melhorar as distâncias

→

Repita

A expressão “tentar melhorar a distância” recebe um nome importante: relaxamento da aresta.

Não é DFS DFS mergulha em um caminho até não conseguir continuar. Dijkstra não faz isso.

Não é BFS pura BFS usa fila comum e escolhe por ordem de chegada, boa quando todo peso vale 1.

É busca por menor custo Dijkstra usa fila de prioridade: sai primeiro quem tem o menor custo acumulado.

Uma forma útil de pensar: Dijkstra parece uma BFS adaptada para grafos com pesos. Em vez de processar por camada, ele processa pelo menor valor de distância conhecido.

O mesmo grafo ponderado da Aula 5

Observe que o caminho visualmente mais “direto” não é necessariamente o mais barato.

Relaxamento: o coração do Dijkstra

Suponha que já sabemos que o custo para chegar em B é 4.

distancia[B] = 4
peso(B,E) = 1

novo_custo = 4 + 1 = 5

distancia[E] = ∞

5 < ∞ ? SIM

distancia[E] = 5

Relaxar uma aresta significa perguntar: “Chegar ao vizinho passando por mim fica mais barato do que o melhor valor conhecido?”

Dijkstra animado: A → G

Fila de prioridade

Regra: o item destacado tem o menor custo e será retirado primeiro. Itens “antigos” podem ficar na fila, mas são ignorados se já existe custo melhor.

Já saiu da fila

Execução passo 0

Clique em “Próximo” ou “Executar”.

Vértice escolhido —

A∞

B∞

C∞

D∞

E∞

F∞

G∞

Qual caminho venceu?

4→

1→

2→

7 custo mínimo de A até G

O caminho A → C → F → G possui o mesmo número de arestas, mas custa 9. Dijkstra escolhe pelo custo acumulado, não pela quantidade de passos.

Dijkstra em C++17

#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

using Aresta = std::pair<int, int>; // vizinho, peso
using Estado = std::pair<int, int>; // distância, vértice

std::vector<int> dijkstra(
    const std::vector<std::vector<Aresta>>& grafo,
    int origem
) {
    const int INF = std::numeric_limits<int>::max();
    std::vector<int> distancia(grafo.size(), INF);
    std::vector<int> anterior(grafo.size(), -1);

    std::priority_queue<
        Estado,
        std::vector<Estado>,
        std::greater<Estado>
    > fila;

    distancia[origem] = 0;
    fila.push({0, origem});

    while (!fila.empty()) {
        auto [dist_atual, atual] = fila.top();
        fila.pop();

        if (dist_atual != distancia[atual])
            continue;

        for (auto [vizinho, peso] : grafo[atual]) {
            int nova_distancia = dist_atual + peso;

            if (nova_distancia < distancia[vizinho]) {
                distancia[vizinho] = nova_distancia;
                anterior[vizinho] = atual;
                fila.push({nova_distancia, vizinho});
            }
        }
    }

    return distancia;
}

int main() {
    std::vector<std::vector<Aresta>> grafo{
        {{1, 4}, {2, 2}},
        {{0, 4}, {3, 5}, {4, 1}},
        {{0, 2}, {4, 7}, {5, 3}},
        {{1, 5}, {6, 6}},
        {{1, 1}, {2, 7}, {6, 2}},
        {{2, 3}, {6, 4}},
        {{3, 6}, {4, 2}, {5, 4}}
    };

    auto distancias = dijkstra(grafo, 0);

    for (int v = 0; v < static_cast<int>(distancias.size()); ++v)
        std::cout << v << ": " << distancias[v] << '\n';
}

std::priority_queue com std::greater funciona como uma fila de prioridade mínima: o menor valor de distância fica disponível primeiro.

BFS × Dijkstra

Característica	BFS	Dijkstra
Estrutura principal	Fila	Fila de prioridade
Pesos das arestas	Iguais	Podem ser diferentes
Critério	Menor nº de arestas	Menor custo acumulado
C++	`std::queue`	`std::priority_queue`
Exemplo	Movimentos do cavalo	Rotas com distâncias/custos

Frase para memorizar: “BFS escolhe por camada. Dijkstra escolhe pelo menor custo conhecido.” DFS não entra nessa escolha porque ela não garante menor caminho: ela apenas aprofunda em um caminho.