Dijkstra's Algorithm

Categoria: Graphs

O problema

Um grafo com arestas ponderadas não tem uma única "distância" entre dois nós da forma como uma grade tem — o caminho mais barato pode ter mais saltos do que um mais caro. Forçar bruta todos os caminhos entre uma origem e cada outro nó é combinatoriamente inviável além de um punhado de nós. O que é necessário é uma forma de construir incrementalmente a verdadeira menor distância até cada nó, sem nunca reexaminar um nó depois que sua menor distância é conhecida com certeza.

A solução

A cada passo, finalize gulosamente o nó mais próximo ainda não finalizado, depois relaxe (potencialmente diminua) a distância provisória de cada um de seus vizinhos através dele. Como todo peso de aresta é não negativo, uma vez que um nó é finalizado — sua menor distância está fixada — nada finalizado depois poderia jamais lhe oferecer um caminho mais barato, já que qualquer caminho desses teria que passar por um nó que está mais longe do que ele já está. Essa única garantia é todo o argumento de correção, e é também exatamente por isso que esse algoritmo quebra no momento em que se permite um peso de aresta negativo.

flowchart LR
    A((A)) -- 1 --> B((B))
    A -- 4 --> C((C))
    B -- 1 --> C
    B -- 5 --> D((D))
    C -- 1 --> D
    A -. 10 .-> D

Exemplo clássico

classic/WeightedGraph é um grafo não direcionado, de pesos não negativos, armazenado como uma lista de adjacência feita à mão, tendo shortestPathFrom(source) — o algoritmo de Dijkstra — como sua operação central. A fronteira é uma java.util.PriorityQueue simples, uma exceção deliberada e documentada à regra usual deste repositório de "sem atalhos do java.util": a estrutura de dados que este módulo demonstra é o próprio algoritmo de grafo — a estratégia de relaxamento guloso de Dijkstra — não a mecânica do heap, que é sua própria estrutura separada, com seu próprio módulo dedicado (futuro) no roteiro deste repositório. WeightedGraphTest cobre um nó isolado inalcançável, um nó cuja menor distância precisa ser relaxada para baixo mais de uma vez (forçando o algoritmo a pular uma entrada de fila obsoleta, já finalizada), e um caminho alternativo pior que não deve sobrescrever uma distância já conhecida e melhor.

Exemplo aplicado: roteamento de liquidação interbancária

applied/InterbankSettlementRouter roteia uma liquidação através de trilhos de bancos correspondentes — saltos no estilo PIX, TED e Boleto, cada um com sua própria tarifa — em vez de assumir um único caminho fixo ou o menor número de saltos. Mover fundos de uma conta de origem até um destino raramente acontece por um único trilho direto: passa por contas correspondentes intermediárias, e a cadeia de saltos mais barata nem sempre é a que tem o menor número de saltos ou o primeiro passo mais barato. Modelar cada trilho conhecido como uma aresta ponderada e rodar Dijkstra a partir da conta de origem encontra a rota de tarifa total mínima em uma única passada. InterbankSettlementRouterTest cobre um caso em que uma rota correspondente de dois saltos supera um trilho direto mais caro, e um caso em que nenhuma cadeia conhecida de trilhos alcança o destino.

Benchmark

./gradlew :graphs:dijkstra:jmh

Execução real (JMH 1.37, JDK 26.0.2, 2 iterações de aquecimento + 3 iterações de medição, 1 fork). Um grafo conectado aleatório, com densidade de arestas mantida em aproximadamente 4 arestas por nó à medida que a contagem de nós aumenta, de modo que V e E crescem juntos:

O custo cresce visivelmente mais rápido do que a contagem de nós sozinha (100x nós -> ~536x mais lento), o que é coerente com o que está de fato sendo medido: tanto V quanto E crescem juntos aqui (densidade de arestas mantida em ~4 por nó), então a carga de trabalho em si cresce mais rápido do que V, e a fila de prioridade com exclusão preguiçosa usada aqui (sem decrease-key; um nó relaxado recebe uma nova entrada de fila em vez disso) faz com que a fila possa conter uma quantidade da ordem de E entradas em vez de V, empurrando a constante real para mais perto de O(E log E) do que o O((V+E) log V) idealizado. De qualquer forma, o formato é inconfundivelmente muito melhor que quadrático e pior que linear — exatamente o território "mais inteligente que força bruta, mas não de graça" que este algoritmo deveria ocupar.

Quando não usar

• Algum peso de aresta pode ser negativo? O argumento guloso de Dijkstra de "uma vez finalizado, nunca revisitado" quebra imediatamente — Bellman-Ford (tolera pesos negativos, detecta ciclos negativos) é a ferramenta correta nesse caso, a um custo mais alto de O(V·E).
• Precisa do caminho mais curto entre todos os pares de nós, não apenas a partir de uma origem? Rodar isso uma vez por nó custa O(V·(V+E) log V); um algoritmo de todos os pares como Floyd-Warshall (O(V^3), mas sem overhead de fila de prioridade por execução) geralmente vence quando a maioria dos pares já é necessária de qualquer forma.
• Grafo não ponderado (toda aresta custa efetivamente o mesmo)? Um BFS simples encontra o caminho mais curto em O(V+E) sem precisar de fila de prioridade alguma — o futuro módulo Graph (BFS/DFS) deste repositório é o ideal para esse caso mais restrito.

Cobertura de testes

100% de cobertura de instruções, 100% de cobertura de branches (JaCoCo). Reproduza você mesmo:

./gradlew :graphs:dijkstra:jacocoTestReport

Relatório em graphs/dijkstra/build/reports/jacoco/test/html/index.html.

Testes unitários

package com.datastructures.graphs.dijkstra.classic;

import org.junit.jupiter.api.Test;

import java.util.Map;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class WeightedGraphTest {

    @Test
    void singleNodeGraphReachesOnlyItself() {
        WeightedGraph<String> graph = new WeightedGraph<>();
        graph.addNode("A");

        Map<String, Long> distances = graph.shortestPathFrom("A");

        assertThat(distances).containsExactly(Map.entry("A", 0L));
        assertThat(graph.nodeCount()).isEqualTo(1);
    }

    @Test
    void addEdgeRejectsANegativeWeight() {
        WeightedGraph<String> graph = new WeightedGraph<>();

        assertThatThrownBy(() -> graph.addEdge("A", "B", -1))
                .isInstanceOf(IllegalArgumentException.class)
                .hasMessageContaining("-1");
    }

    @Test
    void aNodeWithNoPathToTheSourceIsAbsentFromTheResult() {
        WeightedGraph<String> graph = new WeightedGraph<>();
        graph.addEdge("A", "B", 1);
        graph.addNode("Z"); // isolated: no edge connects it to anything

        Map<String, Long> distances = graph.shortestPathFrom("A");

        assertThat(distances).containsOnlyKeys("A", "B");
        assertThat(distances).doesNotContainKey("Z");
    }

    /**
     * A graph shaped so Dijkstra must relax B's and D's tentative distance downward more than
     * once (forcing multiple, decreasing queue entries for the same node — i.e. stale entries
     * that get skipped once the node is already settled) before settling on the true shortest
     * distances.
     */
    @Test
    void dijkstraFindsTheTrueShortestDistancesThroughRelaxationAndSkipsStaleQueueEntries() {
        WeightedGraph<String> graph = new WeightedGraph<>();
        graph.addEdge("A", "B", 1);
        graph.addEdge("A", "C", 4);
        graph.addEdge("B", "C", 1);
        graph.addEdge("C", "D", 1);
        graph.addEdge("B", "D", 5);
        graph.addEdge("A", "D", 10);

        Map<String, Long> distances = graph.shortestPathFrom("A");

        assertThat(distances)
                .containsEntry("A", 0L)
                .containsEntry("B", 1L)
                .containsEntry("C", 2L)
                .containsEntry("D", 3L);
    }

    /**
     * B is settled before C (distance 1 < 2), and B has a very expensive edge to C. That
     * relaxation attempt must be rejected because it's worse than C's already-known distance —
     * the "not an improvement" branch of the relaxation check.
     */
    @Test
    void aWorseAlternatePathDoesNotOverwriteAnAlreadyBetterKnownDistance() {
        WeightedGraph<String> graph = new WeightedGraph<>();
        graph.addEdge("A", "B", 1);
        graph.addEdge("A", "C", 2);
        graph.addEdge("B", "C", 100);

        Map<String, Long> distances = graph.shortestPathFrom("A");

        assertThat(distances).containsEntry("C", 2L);
    }
}

package com.datastructures.graphs.dijkstra.applied;

import org.junit.jupiter.api.Test;

import java.util.Optional;

import static org.assertj.core.api.Assertions.assertThat;

class InterbankSettlementRouterTest {

    private final BankAccount originAccount = new BankAccount("BANK-A", "0001");
    private final BankAccount correspondentAccount = new BankAccount("BANK-B", "0002");
    private final BankAccount destinationAccount = new BankAccount("BANK-C", "0003");
    private final BankAccount unreachableAccount = new BankAccount("BANK-Z", "9999");

    @Test
    void findsTheCheapestFeeAcrossACorrespondentBankHopEvenWhenADirectRailIsMoreExpensive() {
        InterbankSettlementRouter router = new InterbankSettlementRouter();
        router.registerRail(originAccount, destinationAccount, 900); // expensive direct PIX rail
        router.registerRail(originAccount, correspondentAccount, 100); // TED hop
        router.registerRail(correspondentAccount, destinationAccount, 150); // Boleto hop

        Optional<Long> cheapestFee = router.cheapestSettlementFee(originAccount, destinationAccount);

        assertThat(cheapestFee).contains(250L);
    }

    @Test
    void noKnownChainOfRailsReturnsAnEmptyResult() {
        InterbankSettlementRouter router = new InterbankSettlementRouter();
        router.registerRail(originAccount, correspondentAccount, 100);

        Optional<Long> cheapestFee = router.cheapestSettlementFee(originAccount, unreachableAccount);

        assertThat(cheapestFee).isEmpty();
    }
}

Ver relatório completo de cobertura JaCoCo →