O algoritmo de Dijkstra é uma solução clássica para o problema do caminho mínimo em grafos ponderados com arestas não negativas. Sua adaptação para ambientes distribuídos — especialmente sobre frameworks como Hadoop MapReduce — exige uma reformulação conceitual, pois a versão sequenical depende fortemente de estruturas de dados centralizadas (como filas de prioridade) e atualizações iterativas síncronas. Este artigo explora os fundamentos necessários para essa transição, começando pela modelagem eficiente do grafo e da fila de prioridade em Java, seguida por uma implementação sequencial que serve como base para futuras etapas de paralelização.

Para representar o grafo, utilizamos uma estrutura baseada em Map<Vértice, Map<Vértice, Peso>>, onde cada vértice mapeia seus vizinhos e respectivos pesos das arestas. A classe Grafo oferece métodos para construção a partir de arquivos de texto no formato origem destino peso, além de operações básiccas como recuperação de adjacências e contagem de vértices:

import java.io.; import java.util.;

public class Grafo { private final Map> listaAdj;

public Grafo(Map<vertice integer="" map="">> adj) {
    this.listaAdj = new HashMap<>(adj);
}

public static Grafo carregarDeArquivo(String caminho) throws IOException {
    try (BufferedReader leitor = new BufferedReader(
            new InputStreamReader(new FileInputStream(caminho)))) {

        Map<vertice integer="" map="">> adjacencias = new HashMap<>();
        Map<string vertice=""> nomeParaVertice = new HashMap<>();

        String linha;
        while ((linha = leitor.readLine()) != null) {
            String[] partes = linha.trim().split("\\s+");
            if (partes.length != 3) continue;

            String origemNome = partes[0];
            String destinoNome = partes[1];
            int peso = Integer.parseInt(partes[2]);

            Vertice origem = nomeParaVertice.computeIfAbsent(
                origemNome, Vertice::novo);
            Vertice destino = nomeParaVertice.computeIfAbsent(
                destinoNome, Vertice::novo);

            adjacencias.computeIfAbsent(origem, k -> new HashMap<>())
                       .put(destino, peso);
        }
        return new Grafo(adjacencias);
    }
}

public Set<vertice> obterVertices() {
    return Collections.unmodifiableSet(listaAdj.keySet());
}

public Map<vertice integer=""> obterVizinhos(Vertice v) {
    return listaAdj.getOrDefault(v, Collections.emptyMap());
}

public int obterPeso(Vertice u, Vertice v) {
    return obterVizinhos(u).getOrDefault(v, Integer.MAX_VALUE);
}

public int contarVertices() {
    return listaAdj.size();
}

}

</div>A classe `Vertice` encapsula identidade e estado dinâmico (ex.: distância estimada), com sobrescrita adequada de `equals` e `hashCode` para uso em coleções genéricas:

<div>```
package br.infra.algoritmos.grafo;

public class Vertice {
    private final String identificador;
    private int distancia;

    private Vertice(String id, int dist) {
        this.identificador = id;
        this.distancia = dist;
    }

    public static Vertice novo(String id) {
        return new Vertice(id, Integer.MAX_VALUE);
    }

    public String getId() {
        return identificador;
    }

    public int getDistancia() {
        return distancia;
    }

    public void definirDistancia(int d) {
        this.distancia = d;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Vertice vertice = (Vertice) obj;
        return Objects.equals(identificador, vertice.identificador);
    }

    @Override
    public int hashCode() {
        return Objects.hash(identificador);
    }

    @Override
    public String toString() {
        return getId() + "(" + getDistancia() + ")";
    }
}

import java.util.*;

public class FilaPrioridade { private final List elementos = new ArrayList<>();

public void inserir(Vertice v) {
    // Remove instância anterior, se existir
    elementos.removeIf(x -> x.getId().equals(v.getId()));
    
    // Insere mantendo ordem crescente por distância
    int posicao = 0;
    while (posicao < elementos.size() && 
           elementos.get(posicao).getDistancia() <= v.getDistancia()) {
        posicao++;
    }
    elementos.add(posicao, v);
}

public Vertice extrairMinimo() {
    return elementos.isEmpty() ? null : elementos.remove(0);
}

public boolean estaVazia() {
    return elementos.isEmpty();
}

public void imprimir() {
    elementos.forEach(System.out::print);
    System.out.println();
}

}

</div>A implementação sequencial do algoritmo inicializa todas as distâncias com infinito (representado por `Integer.MAX_VALUE`), exceto a fonte, cuja distância é zero. Em seguida, itera enquanto houver vértices na fila: extrai o vértice de menor distância estimada e relaxa todas as suas arestas de saída, atualizando distâncias e reinserindo vértices modificados na fila:

<div>```
package br.infra.algoritmos.dijkstra;

import br.infra.algoritmos.grafo.*;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;

public class DijkstraSequencial {
    public void executar(Grafo grafo, Vertice origem) {
        Map<vertice integer=""> distancias = new HashMap<>();
        FilaPrioridade fila = new FilaPrioridade();

        // Inicialização
        for (Vertice v : grafo.obterVertices()) {
            int dist = v.equals(origem) ? 0 : Integer.MAX_VALUE;
            v.definirDistancia(dist);
            distancias.put(v, dist);
            if (dist != Integer.MAX_VALUE) {
                fila.inserir(v);
            }
        }

        // Loop principal
        while (!fila.estaVazia()) {
            Vertice atual = fila.extrairMinimo();
            int distAtual = atual.getDistancia();

            for (Map.Entry<vertice integer=""> vizinho : 
                 grafo.obterVizinhos(atual).entrySet()) {

                Vertice proximo = vizinho.getKey();
                int pesoAresta = vizinho.getValue();
                int novaDistancia = distAtual + pesoAresta;

                if (novaDistancia < proximo.getDistancia()) {
                    proximo.definirDistancia(novaDistancia);
                    fila.inserir(proximo);
                }
            }
        }

        // Saída formatada
        grafo.obterVertices().forEach(v -> 
            System.out.printf("%s → %d%n", v.getId(), v.getDistancia()));
    }

    public static void main(String[] args) throws IOException {
        Grafo g = Grafo.carregarDeArquivo("dados/grafo.txt");
        DijkstraSequencial dijkstra = new DijkstraSequencial();
        dijkstra.executar(g, Vertice.novo("A"));
    }
}</vertice></vertice>