Abordagens para Resolução de Caminhos Ótimos

A determinação do trajeto de menor custo entre nós em grafos ponderados é um pilar da ciência da computação. A escolha do método depende fundamentalmente da natureza dos pesos das arestas e da escopo da consulta (fonte única versus múltiplas fontes). Quando o grafo contém exclusivamente custos não negativos, técnicas baseadas em ganância oferecem desempenho superior. Na presença de valores negativos, iterações de relaxamento global ou programação dinâmica tornam-se obrigatórias para garantir a exatidão matemática.

Mecanismo Guloso de Dijkstra

Este algoritmo resolve problemas de fonte única assumindo que uma vez selecionado o vértice com a menor distância acumulada, seu valor ótimo é definitivo. A estratégia divide-se em duas operações cíclicas: identificação do nó não processado com o menor custo conhecido e atualização (relaxamento) de seus vizinhos diretos. Para implementações baseadas em matriz de adjacência, a complexidade temporal estabelece-se em O(V²). Um vetor booleano controla a finalização dos nós, impedindo reavaliações desnecessárias.

Implementação refatorada:

void resolverDijkstra(const std::vector<std::vector<long>>& matrizAdj, 
                      size_t indiceFonte, 
                      std::vector<long>& custos) {
    const size_t totalNos = matrizAdj.size();
    custos.assign(totalNos, std::numeric_limits<long>::max());
    custos[indiceFonte] = 0;
    std::vector<bool> finalizados(totalNos, false);

    for (size_t iteracao = 0; iteracao < totalNos; ++iteracao) {
        unsigned noSelecionado = static_cast<unsigned>(-1);
        long menorValor = std::numeric_limits<long>::max();

        for (size_t candidato = 0; candidato < totalNos; ++candidato) {
            if (!finalizados[candidato] && custos[candidato] < menorValor) {
                menorValor = custos[candidato];
                noSelecionado = static_cast<unsigned>(candidato);
            }
        }

        if (noSelecionado == static_cast<unsigned>(-1)) break;
        finalizados[noSelecionado] = true;

        for (size_t vizinho = 0; vizinho < totalNos; ++vizinho) {
            const long pesoAresta = matrizAdj[noSelecionado][vizinho];
            const bool conexaoValida = (pesoAresta != std::numeric_limits<long>::max());
            
            if (conexaoValida && !finalizados[vizinho]) {
                const long trajetoAlternativo = custos[noSelecionado] + pesoAresta;
                if (trajetoAlternativo < custos[vizinho]) {
                    custos[vizinho] = trajetoAlternativo;
                }
            }
        }
    }
}

Relaxamento Iterativo de Bellman-Ford

Diferente da abordagem anterior, este método não fixa permanentemente os vértices em uma única passagem. Em vez disso, ele percorre sistematicamente todas as conexões do grafo, tentando reduzir os valores da tabela de distâncias. Para um grafo com V vértices, o caminho mínimo é garantido após no máximo V-1 ciclos completos de verificação. A presença de pesos negativos não invalida o processo, embora ciclos de peso negativo tornem o problema matematicamente indefinido. Uma otimização prática interrompe o laço principle quando uma iteração completa não produz nenhuma modificação nos custos.

Estrutura lógica adaptada:

bool executarBellmanFord(const std::vector<std::vector<long>>& grafo,
                         size_t verticeInicial,
                         std::vector<long>& tabelaCustos) {
    const size_t quantidadeVertices = grafo.size();
    tabelaCustos.assign(quantidadeVertices, std::numeric_limits<long>::max());
    tabelaCustos[verticeInicial] = 0;
    bool ocorreuMudanca = true;
    size_t rodadaAtual = 1;

    while (rodadaAtual <= quantidadeVertices && ocorreuMudanca) {
        ocorreuMudanca = false;
        for (size_t origem = 0; origem < quantidadeVertices; ++origem) {
            if (tabelaCustos[origem] == std::numeric_limits<long>::max()) continue;
            for (size_t destino = 0; destino < quantidadeVertices; ++destino) {
                const long custoTransicao = grafo[origem][destino];
                if (custoTransicao != std::numeric_limits<long>::max()) {
                    const long novoValor = tabelaCustos[origem] + custoTransicao;
                    if (novoValor < tabelaCustos[destino]) {
                        tabelaCustos[destino] = novoValor;
                        ocorreuMudanca = true;
                    }
                }
            }
        }
        ++rodadaAtual;
    }

    for (size_t u = 0; u < quantidadeVertices; ++u) {
        for (size_t v = 0; v < quantidadeVertices; ++v) {
            const long peso = grafo[u][v];
            if (peso != std::numeric_limits<long>::max() &&
                tabelaCustos[u] + peso < tabelaCustos[v]) {
                return false; // Ciclo de peso negativo detectado
            }
        }
    }
    return true;
}

Programação Dinâmica de Floyd-Warshall

Projetado para calcular simultaneamente as rotas ideais entre todos os pares de vértices, este algoritmo emprega o princípio de optimalidade da programação dinâmica. O núcleo do processamento testa iterativamente se um vértice pivô k atua como atalho para melhorar a conexão entre i e j. A matriz de resultados é inicializada com os pesos diretos das arestas, definindo a diagonal principle como zero. A ordenação dos laços aninhados garante que, ao avaliar o pivô k, todas as combinações anteriores (k-1) já estejam consolidadas, permitindo a reconstrução progressiva das rotas.

Exemplo de codificação:

void calcularMatrizTodosPares(const std::vector<std::vector<long>>& pesosOriginais,
                              std::vector<std::vector<long>>& distanciasFinais) {
    const size_t tamanho = pesosOriginais.size();
    distanciasFinais.assign(tamanho, std::vector<long>(tamanho, std::numeric_limits<long>::max()));

    for (size_t linha = 0; linha < tamanho; ++linha) {
        for (size_t coluna = 0; coluna < tamanho; ++coluna) {
            distanciasFinais[linha][coluna] = (linha == coluna) ? 0 : pesosOriginais[linha][coluna];
        }
    }

    for (size_t pivote = 0; pivote < tamanho; ++pivote) {
        for (size_t i = 0; i < tamanho; ++i) {
            if (distanciasFinais[i][pivote] == std::numeric_limits<long>::max()) continue;
            for (size_t j = 0; j < tamanho; ++j) {
                if (distanciasFinais[pivote][j] != std::numeric_limits<long>::max()) {
                    const long caminhoViaPivot = distanciasFinais[i][pivote] + distanciasFinais[pivote][j];
                    if (caminhoViaPivot < distanciasFinais[i][j]) {
                        distanciasFinais[i][j] = caminhoViaPivot;
                    }
                }
            }
        }
    }
}