Grafos: Caminhos Mínimos (Shortest Path)

Motivadores e a Queda da BFS

A busca em largura (BFS) é espetacular quando queremos a rota mais rápida, assumindo que o desgaste de cruzar cada cidade seja estritamente igual (unitário).

No mundo real, as estradas têm pedágios diferentes, e viajar de São Paulo -> Rio de Janeiro pode custar 8 horas via BR-116 ou 6 horas de avião. Entram as arestas ponderadas (com peso) w(u, v). O nosso alvo não é cruzar menos estados (menos arestas), mas achar a somatória vetorial cujo custo final seja o menor em combustível/tempo.

O roteiro acima comprova a tese: A rota de menor custo salta 3 cidades (A->C->B->D), ignorando a opção mais direta (A->B->D) porque a viagem é bem mais densa e custosa na estrada principal de peso 10.

Os Grandes Campeões do Shortest Path

A depender do comportamento do grafo (se as estradas te devolvem o dinheiro = pesos negativos, ou se você quer as rotas completas universais), escolhemos um campeão correspondente de desempenho:

Dijkstra (\(\mathcal{O}(E \log V)\)):
- Rei dos pesos Positivos: Usa a lógica Gulosa pareado a um Min-Heap (Fila de Prioridade) para sempre expandir as bolhas pelo fronte mais barato. Jamais use em arestas cujo peso \(< 0\), pois ele assume que todo caminho futuro será invariavelmente mais caro e não volta atrás para refatorar!
Bellman-Ford (\(\mathcal{O}(V \cdot E)\)):
- Detectando Buracos de Minhoca: Aceita pesos negativos! Ele flexiona / relaxa todas as arestas extenuantes \(V-1\) vezes. O grande trunfo: se rodarmos mais 1 vez e algum peso abaixar de novo, significa que há um looping decrescendo ao infinito (um Ciclo Negativo detectado na topografia)!
Floyd-Warshall (\(\mathcal{O}(V^3)\)):
- Rei do Todos para Todos: Programação Dinâmica brutal e elegante que monta uma Matriz global. Você descobre simultaneamente o melhor trajeto indo de Qualquer Cidade (i) \(\rightarrow\) Qualquer Outra (j). Contudo, seu peso restringe usos em limites \(V \le 400\).

Implementando e Testando: O Algoritmo de Dijkstra

Na maioria das disputas de competição, modelamos os vértices de grafos com pesos na notação <VerticeDestino, Peso>. Veja como Dijkstra é esteticamente codificável usando um heap (Priority Queue) reverso:

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;

// alias para os tipos para facilitar a leitura
typedef pair<int, int> pii; 
const int INF = 1e9; // 1 Bilhão (Infinito Seguro)

// Dijkstra padrão de nó fixo (Inicio -> Qualque um)
vector<int> rodarDijkstra(int N, vector<vector<pii>>& adj, int inicio) {
    // Tabela global de distncias começam pessimistas
    vector<int> dist(N, INF);
    dist[inicio] = 0;
    
    // priority_queue inverte ordenação naturalmente (Max-Heap), então tipamos std::greater
    // Na fila temos: pair< CustoAteAqui, VerticeAtual >
    priority_queue<pii, vector<pii>, greater<pii>> heap;
    heap.push({0, inicio});

    while(!heap.empty()) {
        int custo_chegada = heap.top().first;
        int u = heap.top().second;
        heap.pop();

        // Podagem drástica: se eu já tirei um custo mais barato pra esse nó da fila, ignora o espelho tardio
        if(custo_chegada > dist[u]) continue; 

        // Expansão relaxativa ao fronte de batalha
        for(auto& aresta : adj[u]) {
            int v = aresta.first;
            int peso_via = aresta.second;

            // Relaxamento
            if(dist[u] + peso_via < dist[v]) {
                dist[v] = dist[u] + peso_via;
                heap.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

void executando_testes() {
    int V = 4;
    vector<vector<pii>> adj(V);
    
    // Convertendo o grafo Mermaid do capítulo para nossa Array 
    // Indice: 0(A), 1(B), 2(C), 3(D)
    adj[0].push_back({1, 10}); // A -> B (10)
    adj[0].push_back({2, 3});  // A -> C (3)
    adj[2].push_back({1, 1});  // C -> B (1)
    adj[1].push_back({3, 2});  // B -> D (2)
    adj[2].push_back({3, 8});  // C -> D (8)

    // O melhor caminho simulado de A (0 -> todos)
    vector<int> resolucao = rodarDijkstra(V, adj, 0);

    // O Mermaid previa explicitamente os limites:
    assert(resolucao[0] == 0); // Para si meso
    assert(resolucao[2] == 3); // Para C é a via reta
    assert(resolucao[1] == 4); // Para B vale muito mais ir pra C(3) e pegar B(+1) = 4 !
    assert(resolucao[3] == 6); // Destino final: C(1) + B(1) + D(2) = 6 !

    cout << "[✅] Lógica Gulosa e Heap Minimo validados no Caminho Mínimo.\n";
}

int main() {
    executando_testes();
    return 0;
}

Exercícios Sugeridos (Pratique Relaxamentos)

Identifique a modelagem dos problemas. É peso unitário? Mude para matriz 0-1 e rode BFS. Requer ir em reinos isolados usando portais instáveis no Multiverso voltando no tempo (custo < 0)? Esqueça as filas prioritárias e lance Bellman-Ford sem olhar para trás!