Algoritmo de Dijkstra — Caminho Mínimo em Grafos

Definição

O Algoritmo de Dijkstra é uma técnica usada para encontrar o caminho mais curto entre um vértice de origem e todos os outros vértices de um grafo com pesos não negativos.

Ele calcula a menor distância entre a origem e os demais vértices, avançando sempre pelo vértice com o menor custo conhecido até visitar todos os caminhos possíveis.

Por que usar

Resolve de forma eficiente o problema de caminho mínimo;
Suporta grafos direcionados e não direcionados;
É amplamente usado em mapas, redes de computadores, jogos e roteamento;
Serve de base para algoritmos mais avançados (como o A*).

Requisitos

Funciona apenas com pesos positivos ou nulos;
Representação com listas de adjacência ou matrizes;
Ideal com fila de prioridade (heap).

Exemplo prático (Python)

import heapq

def dijkstra(grafo, origem):
    distancias = {v: float('inf') for v in grafo}
    distancias[origem] = 0
    fila = [(0, origem)]

    while fila:
        atual_dist, atual_vertice = heapq.heappop(fila)

        if atual_dist > distancias[atual_vertice]:
            continue

        for vizinho, peso in grafo[atual_vertice]:
            distancia = atual_dist + peso
            if distancia < distancias[vizinho]:
                distancias[vizinho] = distancia
                heapq.heappush(fila, (distancia, vizinho))

    return distancias

Exemplo de uso

grafo = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}

resultado = dijkstra(grafo, 'A')
print(resultado)  # Saída: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Visualização

Grafo com pesos:
A --1--> B --2--> C --1--> D
 \        \
  \        \--5--> D
   \--4--> C

Saída

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

'A': 0 → custo de A até A é 0
'B': 1 → menor caminho de A para B custa 1
'C': 3 → menor caminho de A para C custa 3
'D': 4 → menor caminho de A para D custa 4