Equipe Rust Brasil 9 min de leitura

Algoritmo de Dijkstra em Rust

Implementação completa do algoritmo de Dijkstra em Rust com BinaryHeap, reconstrução de caminho, diagramas visuais e análise de complexidade.

rust algoritmos grafos dijkstra caminho-minimo

O algoritmo de Dijkstra é o método mais eficiente para encontrar o caminho mais curto de um vértice de origem a todos os outros vértices em um grafo com pesos não negativos nas arestas. Criado por Edsger Dijkstra em 1956, é um dos algoritmos mais importantes da ciência da computação e continua sendo amplamente usado em sistemas de navegação GPS, roteamento de pacotes em redes, jogos e otimização logística.

Em Rust, a implementação usa BinaryHeap (fila de prioridade baseada em heap máximo) invertido para funcionar como heap mínimo, combinado com listas de adjacência. O sistema de tipos do Rust garante segurança de memória sem overhead, tornando a implementação tanto segura quanto performática.

Como Funciona

O Dijkstra é um algoritmo guloso (greedy) que mantém uma tabela de distâncias mínimas conhecidas e, a cada passo, escolhe o vértice não processado com a menor distância acumulada.

  1. Inicializa a distância da origem como 0 e todos os outros como infinito.
  2. Insere a origem na fila de prioridade (min-heap).
  3. Remove o vértice com menor distância da fila.
  4. Para cada vizinho, calcula a distância passando pelo vértice atual.
  5. Se essa distância for menor que a conhecida, atualiza e insere na fila.
  6. Repete até que a fila esteja vazia.

Diagrama Visual — Atualização de Distâncias

Grafo de exemplo:

        (0)
       / | \
     4/  2|  \1
     /   |   \
   (1)  (2)  (3)
    |   / \    |
   1|  3/  \1  |5
    | /    \  |
   (4)-----(5)
       2

Arestas e pesos:

0-1: 4,  0-2: 2,  0-3: 1
1-4: 1,  2-4: 3,  2-5: 1
3-5: 5,  4-5: 2

Execução a partir do vértice 0:

Passo | Processa | Fila (distância, vértice) | dist[0] | dist[1] | dist[2] | dist[3] | dist[4] | dist[5]
------|----------|---------------------------|---------|---------|---------|---------|---------|--------
Init  |    -     | [(0,0)]                   |    0    |   INF   |   INF   |   INF   |   INF   |   INF
  1   |    0     | [(1,3),(2,2),(4,1)]        |    0    |    4    |    2    |    1    |   INF   |   INF
  2   |    3     | [(2,2),(4,1),(6,5)]        |    0    |    4    |    2    |    1    |   INF   |    6
  3   |    2     | [(3,5),(4,1),(5,4)]        |    0    |    4    |    2    |    1    |    5    |    3
  4   |    5     | [(4,1),(5,4),(5,2)]        |    0    |    4    |    2    |    1    |    5    |    3
  5   |    1     | [(5,4),(5,2)]              |    0    |    4    |    2    |    1    |    5    |    3
  6   |    4     | [(5,2)]                    |    0    |    4    |    2    |    1    |    5    |    3
  7   |    -     | []                         |    0    |    4    |    2    |    1    |    5    |    3

Resultado: distâncias mínimas a partir de 0: [0, 4, 2, 1, 5, 3]

Caminho mais curto de 0 a 5: 0 -> 2 -> 5 (distância = 3)

Representação do Grafo

Para Dijkstra, cada aresta precisa de um peso. Representamos com lista de adjacência onde cada vizinho é um par (destino, peso).

/// Grafo ponderado representado como lista de adjacência.
/// grafo[u] contém pares (vizinho, peso) para cada aresta saindo de u.
fn criar_grafo(num_vertices: usize) -> Vec<Vec<(usize, u64)>> {
    let mut grafo = vec![vec![]; num_vertices];

    // Arestas bidirecionais com peso
    let arestas = [
        (0, 1, 4), (0, 2, 2), (0, 3, 1),
        (1, 4, 1), (2, 4, 3), (2, 5, 1),
        (3, 5, 5), (4, 5, 2),
    ];

    for (u, v, peso) in arestas {
        grafo[u].push((v, peso));
        grafo[v].push((u, peso));
    }

    grafo
}

Complexidade

CasoTempoEspaço
MelhorO(E log V)O(V + E)
MédioO((V + E) log V)O(V + E)
PiorO((V + E) log V)O(V + E)

Onde V = número de vértices e E = número de arestas.

  • Tempo O((V + E) log V): cada vértice é inserido na fila pelo menos uma vez (O(V log V)) e cada aresta pode gerar uma inserção na fila (O(E log V)).
  • Espaço O(V + E): armazena o grafo (O(V + E)), o vetor de distâncias (O(V)) e a fila de prioridade (até O(V) elementos úteis, podendo acumular entradas duplicadas).
  • Com heap de Fibonacci, a complexidade cai para O(V log V + E), mas a biblioteca padrão do Rust usa BinaryHeap.

Implementação em Rust

Dijkstra com BinaryHeap

O BinaryHeap de Rust é um max-heap. Para usá-lo como min-heap, invertemos a ordenação usando std::cmp::Reverse ou implementando Ord com comparação invertida.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

/// Calcula a menor distância de `origem` a todos os vértices.
/// Retorna vetor de distâncias (u64::MAX = inalcançável).
fn dijkstra(grafo: &Vec<Vec<(usize, u64)>>, origem: usize) -> Vec<u64> {
    let n = grafo.len();
    let mut dist = vec![u64::MAX; n];
    let mut heap = BinaryHeap::new();

    dist[origem] = 0;
    heap.push(Reverse((0u64, origem))); // (distância, vértice)

    while let Some(Reverse((custo, u))) = heap.pop() {
        // Se já encontramos um caminho melhor, ignora
        if custo > dist[u] {
            continue;
        }

        for &(vizinho, peso) in &grafo[u] {
            let nova_dist = custo + peso;
            if nova_dist < dist[vizinho] {
                dist[vizinho] = nova_dist;
                heap.push(Reverse((nova_dist, vizinho)));
            }
        }
    }

    dist
}

fn main() {
    let mut grafo = vec![vec![]; 6];
    let arestas = [
        (0, 1, 4), (0, 2, 2), (0, 3, 1),
        (1, 4, 1), (2, 4, 3), (2, 5, 1),
        (3, 5, 5), (4, 5, 2),
    ];
    for (u, v, peso) in arestas {
        grafo[u].push((v, peso));
        grafo[v].push((u, peso));
    }

    let dist = dijkstra(&grafo, 0);
    for (v, d) in dist.iter().enumerate() {
        if *d == u64::MAX {
            println!("Distância de 0 a {}: inalcançável", v);
        } else {
            println!("Distância de 0 a {}: {}", v, d);
        }
    }
    // Saída:
    // Distância de 0 a 0: 0
    // Distância de 0 a 1: 4
    // Distância de 0 a 2: 2
    // Distância de 0 a 3: 1
    // Distância de 0 a 4: 5
    // Distância de 0 a 5: 3
}

Dijkstra com Reconstrução de Caminho

use std::cmp::Reverse;
use std::collections::BinaryHeap;

/// Retorna (distâncias, predecessores) a partir de `origem`.
fn dijkstra_com_caminho(
    grafo: &Vec<Vec<(usize, u64)>>,
    origem: usize,
) -> (Vec<u64>, Vec<Option<usize>>) {
    let n = grafo.len();
    let mut dist = vec![u64::MAX; n];
    let mut predecessor: Vec<Option<usize>> = vec![None; n];
    let mut heap = BinaryHeap::new();

    dist[origem] = 0;
    heap.push(Reverse((0u64, origem)));

    while let Some(Reverse((custo, u))) = heap.pop() {
        if custo > dist[u] {
            continue;
        }

        for &(vizinho, peso) in &grafo[u] {
            let nova_dist = custo + peso;
            if nova_dist < dist[vizinho] {
                dist[vizinho] = nova_dist;
                predecessor[vizinho] = Some(u);
                heap.push(Reverse((nova_dist, vizinho)));
            }
        }
    }

    (dist, predecessor)
}

/// Reconstrói o caminho do `origem` até `destino` usando predecessores.
fn reconstruir_caminho(
    predecessor: &Vec<Option<usize>>,
    origem: usize,
    destino: usize,
) -> Option<Vec<usize>> {
    let mut caminho = Vec::new();
    let mut atual = destino;

    // Se o destino não tem predecessor e não é a origem, não há caminho
    if predecessor[destino].is_none() && destino != origem {
        return None;
    }

    while atual != origem {
        caminho.push(atual);
        match predecessor[atual] {
            Some(pred) => atual = pred,
            None => return None,
        }
    }
    caminho.push(origem);
    caminho.reverse();
    Some(caminho)
}

fn main() {
    let mut grafo = vec![vec![]; 6];
    let arestas = [
        (0, 1, 4), (0, 2, 2), (0, 3, 1),
        (1, 4, 1), (2, 4, 3), (2, 5, 1),
        (3, 5, 5), (4, 5, 2),
    ];
    for (u, v, peso) in arestas {
        grafo[u].push((v, peso));
        grafo[v].push((u, peso));
    }

    let (dist, predecessor) = dijkstra_com_caminho(&grafo, 0);

    // Mostra caminho mínimo para cada vértice
    for destino in 0..grafo.len() {
        if dist[destino] == u64::MAX {
            println!("Vértice {}: inalcançável", destino);
        } else if let Some(caminho) = reconstruir_caminho(&predecessor, 0, destino) {
            println!(
                "Vértice {} (dist={}): {:?}",
                destino, dist[destino], caminho
            );
        }
    }
    // Saída:
    // Vértice 0 (dist=0): [0]
    // Vértice 1 (dist=4): [0, 1]
    // Vértice 2 (dist=2): [0, 2]
    // Vértice 3 (dist=1): [0, 3]
    // Vértice 4 (dist=5): [0, 1, 4]
    // Vértice 5 (dist=3): [0, 2, 5]
}

Exemplo de Execução

Considere um mapa rodoviário simplificado:

    São Paulo --(400)--> Campinas
        |                    |
      (100)                (200)
        |                    |
        v                    v
    Santos ---(350)---> Ribeirão Preto
        |                    |
      (500)                (150)
        |                    |
        v                    v
    Curitiba <--(300)--- Uberlândia

Vértices: 0=SP, 1=Campinas, 2=Santos, 3=R.Preto, 4=Curitiba, 5=Uberlândia

Dijkstra a partir de São Paulo (0):

Inicialização: dist = [0, INF, INF, INF, INF, INF]

Passo 1: Processa SP(0), dist=0
  -> Campinas: 0+400=400 < INF, atualiza dist[1]=400
  -> Santos:   0+100=100 < INF, atualiza dist[2]=100
  dist = [0, 400, 100, INF, INF, INF]

Passo 2: Processa Santos(2), dist=100
  -> R.Preto:  100+350=450 < INF, atualiza dist[3]=450
  -> Curitiba: 100+500=600 < INF, atualiza dist[4]=600
  dist = [0, 400, 100, 450, 600, INF]

Passo 3: Processa Campinas(1), dist=400
  -> R.Preto: 400+200=600 > 450, não atualiza
  dist = [0, 400, 100, 450, 600, INF]

Passo 4: Processa R.Preto(3), dist=450
  -> Uberlândia: 450+150=600 < INF, atualiza dist[5]=600
  dist = [0, 400, 100, 450, 600, 600]

Passo 5: Processa Curitiba(4), dist=600 (ou Uberlândia, mesma distância)
Passo 6: Processa Uberlândia(5), dist=600
  -> Curitiba: 600+300=900 > 600, não atualiza

Resultado final: SP->SP=0, SP->Campinas=400, SP->Santos=100,
                 SP->R.Preto=450, SP->Curitiba=600, SP->Uberlândia=600

Variações e Otimizações

1. Dijkstra com Parada Antecipada

Se você precisa apenas da distância para um destino específico, pode encerrar assim que esse vértice for processado (removido da fila):

if u == destino {
    return dist[destino];
}

2. Dijkstra Bidirecional

Executa Dijkstra simultaneamente da origem e do destino, parando quando as duas buscas se encontram. Reduz significativamente o número de vértices explorados em grafos grandes.

3. A* (A-estrela)

Uma extensão do Dijkstra que usa uma heurística para guiar a busca na direção do destino. É mais eficiente que Dijkstra para encontrar o caminho entre dois pontos específicos quando uma boa heurística está disponível (por exemplo, distância euclidiana em mapas).

Quando Usar

Use Dijkstra quando:

  • O grafo tem arestas com pesos não negativos.
  • Precisa do caminho mais curto de um vértice a todos os outros (ou a um destino específico).
  • O grafo é esparso (E muito menor que V^2) — a representação com lista de adjacência e heap binário é ideal.
  • Está implementando roteamento em redes, navegação GPS ou otimização logística.

Evite Dijkstra quando:

  • O grafo tem arestas com peso negativo — use Bellman-Ford.
  • O grafo não tem pesos — use BFS, que é mais simples e tem mesma complexidade.
  • Precisa de todos os pares de caminhos mínimos — use Floyd-Warshall.

Comparação com Outros Algoritmos

CaracterísticaDijkstraBellman-FordFloyd-WarshallBFS
Pesos negativosNaoSimSimNao (sem peso)
Ciclos negativosNao detectaDetectaDetectaN/A
FonteÚnicaÚnicaTodos os paresÚnica
ComplexidadeO((V+E) log V)O(V * E)O(V^3)O(V + E)
Melhor paraGrafos esparsosPesos negativosGrafos densos/pequenosSem peso
Reconstrução de caminhoSimSimSimSim

Exercícios Práticos

  1. Custo mínimo de voo: Dados N aeroportos e M voos com custos, encontre o voo mais barato de uma cidade de origem a uma cidade de destino usando Dijkstra. Reconstrua o itinerário completo.

  2. Labirinto ponderado: Dada uma matriz NxN onde cada célula tem um custo para atravessar, encontre o caminho de custo mínimo do canto superior esquerdo ao inferior direito.

  3. Rede de computadores: Dados N computadores conectados por links com latência variável, encontre o caminho com menor latência total entre dois computadores. Identifique os links que são gargalos.

  4. Dijkstra com no máximo K arestas: Modifique o Dijkstra para encontrar o caminho mais curto usando no máximo K arestas. (Dica: adicione o número de arestas ao estado.)

Veja Também