O Problema da Busca em Profundidade (DFS) em Grafos

Considere o problema clássico de encontrar o caminho mais curto em um grafo ponderado. Uma abordagem inicial, para quem acabou de aprender a busca em profundidade (DFS), pode ser explorar todos os caminhos recursivamente. No entanto, isso leva a uma ineficiência drástica.

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

const long long INF = LLONG_MAX;

struct Edge {
    int destination;
    int weight;
};

class ShortestPathFinder {
    int num_nodes;
    vector<vector<Edge>> adjacency_list;
    vector<long long> shortest_distances;

    void explorePaths(int current_node, long long current_distance) {
        for (const auto& edge : adjacency_list[current_node]) {
            long long new_distance = current_distance + edge.weight;
            if (new_distance < shortest_distances[edge.destination]) {
                shortest_distances[edge.destination] = new_distance;
                explorePaths(edge.destination, new_distance);
            }
        }
    }

public:
    ShortestPathFinder(int n) : num_nodes(n), adjacency_list(n + 1), shortest_distances(n + 1, INF) {}

    void addEdge(int from, int to, int weight) {
        adjacency_list[from].push_back({to, weight});
    }

    vector<long long> computeDistances(int start_node) {
        shortest_distances[start_node] = 0;
        explorePaths(start_node, 0);
        return shortest_distances;
    }
};

int main() {
    int nodes, edges, start;
    cin >> nodes >> edges >> start;

    ShortestPathFinder solver(nodes);
    for (int i = 0; i < edges; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        solver.addEdge(u, v, w);
    }

    vector<long long> distances = solver.computeDistances(start);
    for (int i = 1; i <= nodes; ++i) {
        cout << distances[i] << (i < nodes ? " " : "\n");
    }
    return 0;
}

Este código sofre de uma complexidade exponencial no pior caso. Embora utilize um vetor shortest_distances para registrar o menor custo encontrado até cada nó, ele não impede a reexploração do mesmo nó através de caminhos diferentes. Um nó pode ser atualizado e reenfileirado na recursão múltiplas vezes, resultando em uma explosão combinatória. Esta implementação recursiva não constitui uma busca com memorização verdadeira.

Bellman-Ford: Um Fundamento Baseado em Programação Dinâmica

O algoritmo de Bellman-Ford revela a ligação fundamental entre caminhos mais curtos e a Programação Dinâmica (DP). Sua implementação canônica baseia-se na relaxação de arestas repetida V-1 vezes, onde V é o número de vértices. A ideia central é a seguinte: após k iterações, encontramos o caminho mais curto de comprimento máximo k (em número de arestas). Formalmente, a transição de estado é:

distancia_k[v] = min(distancia_{k-1}[v], min_{u}(distancia_{k-1}[u] + peso(u, v)))

Essa é, em essência, uma formulação recursiva de DP com sobreposição de subproblemas, onde a dimensão do "estágio" é o número de arestas usadas. As implementações otimizadas frequentemente usam um único vetor e o atualizam iterativamente, aproveitando a otimização de array rotativo.

Dijkstra: Otimização com Estratégia Gulosa

O algoritmo de Dijkstra oferece um desempenho superior para grafos com arestas de peso não-negativos. Ele utiliza uma fila de prioridade para selecionar, em cada etapa, o nó com a menor distância provisória que ainda não foi finalizado. Esta é uma abordagem gulosa: uma vez que um nó é "finalizado" (extraído da fila de prioridade), sua distância é garantidamente a menor possível. Isso elimina a necessidade de múltiplas passagens como no Bellman-Ford, resultando em uma complexidade O(E log V). A forma gulosa de Dijkstra também pode ser enquadrada dentro de uma estrutura de DP, onde o estado é simplesmente o nó atual e a transição segue a ordem crescente das distâncias.

Memorização e Programação Dinâmica: Uma Distinção Crítica

A busca com memorização é, na prática, uma implementação recursiva da programação dinâmica. O princípio chave é que uma vez que o valor ótimo para um subproblema (definido por um estado único) é calculado, ele é armazenado e retornado imediatamente se o mesmo estado for encontrado novamente. Isso transforma a complexidade de exponencial para polinomial.

Considere um problema clássico como a Mochila 0/1. Uma implementação recursiva com memorização seria:

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_ITEMS = 100;
const int MAX_CAPACITY = 1000;

int weights[MAX_ITEMS + 1];
int values[MAX_ITEMS + 1];
int memoization_table[MAX_ITEMS + 1][MAX_CAPACITY + 1];

int solveKnapsack(int item_idx, int remaining_capacity) {
    // Checar se o estado já foi calculado
    if (memoization_table[item_idx][remaining_capacity] != -1) {
        return memoization_table[item_idx][remaining_capacity];
    }
    // Caso base: nenhum item restante ou capacidade zerada
    if (item_idx == 0 || remaining_capacity == 0) {
        return 0;
    }
    // Opção 1: Não incluir o item atual
    int result = solveKnapsack(item_idx - 1, remaining_capacity);
    // Opção 2: Incluir o item atual, se houver capacidade
    if (weights[item_idx] <= remaining_capacity) {
        int value_with_item = solveKnapsack(item_idx - 1, remaining_capacity - weights[item_idx]) + values[item_idx];
        result = max(result, value_with_item);
    }
    // Armazenar o resultado no estado (item_idx, remaining_capacity)
    return memoization_table[item_idx][remaining_capacity] = result;
}

int main() {
    int n, capacity;
    cin >> n >> capacity;
    for (int i = 1; i <= n; ++i) {
        cin >> weights[i] >> values[i];
    }
    memset(memoization_table, -1, sizeof(memoization_table));
    cout << solveKnapsack(n, capacity) << endl;
    return 0;
}

Aqui, o par (item_idx, remaining_capacity) define unicamente um estado. A tabela memoization_table garante que a computação para cada estado ocorra apenas uma vez. No exemplo inicial do caminho mais curto com DFS, o "estado" (apenas o nó atual) não era suficiente para determinar um resultado único, pois o custo até aquele nó dependia do caminho percorrido, violando o princípio da subestrutura ótima e da ausência de efeito futuro de forma efetiva. A memorização verdadeira requer que o estado capture toda a informação relevante.

Conectando os Conceitos

Os algoritmos de caminho mais curto são manifestações específicas de problemas de programação dinâmica. O Floyd-Warshall, por exemplo, é claramente um algoritmo de DP com três dimensões de estado: dp[k][i][j] = caminho mais curto de i para j usando apenas vértices intermediários de um conjunto {1, ..., k}. A transição entre estágios k permite reutilizar soluções de subproblemas menores.

A escolha entre implementação iterativa (tabulação) ou recursiva (meomrização) é frequentemente uma questão de preferência e otimização de espaço. A busca com memorização pode ser mais intuitiva para modelar certos problemas, enquanto a tabulação iterativa pode oferecer controle mais preciso sobre a ordem de cálculo e o uso de memória.

Compreender essa essência unificadora permite ao desenvolvedor algorítmico migrar técnicas e insights entre diferentes domínios de problemas, desde rotas em mapas até sequenciamento de decisões em economia computacional.