Algoritmo de Dijkstra

O algoritmo de Dijkstra, criado por Edsger Dijkstra em 1956, calcula o menor caminho entre um nó e todos os outros em um grafo com pesos. O simulador mostra em cada passo qual nó foi escolhido, quais arestas foram relaxadas e como a tabela de distâncias muda, exatamente como em um exercício resolvido de estrutura de dados.

Passo a Passo do Algoritmo

1. Defina distância 0 para a origem e ∞ para todos os outros nós.
2. Escolha o nó não visitado com a menor distância e marque-o como visitado.
3. Para cada vizinho não visitado, calcule distância do nó atual + peso da aresta.
4. Se esse valor for menor que a distância atual do vizinho, atualize e guarde o nó atual como “anterior”.
5. Repita até visitar todos os nós alcançáveis.
6. Para reconstruir o caminho, siga os “anteriores” do destino até a origem.

Dijkstra em Python (com heap)

import heapq

def dijkstra(grafo, origem):
    dist = {n: float("inf") for n in grafo}
    dist[origem] = 0
    fila = [(0, origem)]
    while fila:
        d, u = heapq.heappop(fila)
        if d > dist[u]:
            continue
        for v, peso in grafo[u]:
            if d + peso < dist[v]:
                dist[v] = d + peso
                heapq.heappush(fila, (dist[v], v))
    return dist

grafo = {"A": [("B", 4), ("C", 2)], "B": [("D", 10)], "C": [("E", 3)],
         "D": [], "E": [("D", 4)]}
print(dijkstra(grafo, "A"))

Dijkstra em C (versão O(V²))

#define V 6
#define INF 1000000

void dijkstra(int g[V][V], int origem, int dist[V]) {
    int visitado[V] = {0};
    for (int i = 0; i < V; i++) dist[i] = INF;
    dist[origem] = 0;
    for (int k = 0; k < V; k++) {
        int u = -1;
        for (int i = 0; i < V; i++)
            if (!visitado[i] && (u == -1 || dist[i] < dist[u])) u = i;
        if (dist[u] == INF) break;
        visitado[u] = 1;
        for (int v = 0; v < V; v++)
            if (g[u][v] && dist[u] + g[u][v] < dist[v])
                dist[v] = dist[u] + g[u][v];
    }
}

Dijkstra em Java

int[] dijkstra(List<List<int[]>> adj, int origem) {
    int[] dist = new int[adj.size()];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[origem] = 0;
    PriorityQueue<int[]> fila = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    fila.add(new int[]{origem, 0});
    while (!fila.isEmpty()) {
        int[] atual = fila.poll();
        int u = atual[0];
        if (atual[1] > dist[u]) continue;
        for (int[] aresta : adj.get(u)) {
            int v = aresta[0], peso = aresta[1];
            if (dist[u] + peso < dist[v]) {
                dist[v] = dist[u] + peso;
                fila.add(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

Perguntas Frequentes

Ferramentas Relacionadas

• Busca binária
• Árvore binária de busca
• Calculadora de sub-rede IPv4
• Algoritmos de ordenação