O peso precisa somar custo, sem nunca devolvê-lo.
O requisito é w(u, v) ≥ 0 para cada aresta. Com uma aresta negativa, uma rota descoberta mais tarde poderia baratear um vértice já finalizado; a escolha gulosa deixaria de ser segura.
03 / grafos
ver A* Dijkstra's Algorithm.
Escolha o custo conhecido mais baixo e relaxe o mapa.
visualização passo a passo
Encontra o menor caminho quando os pesos não são negativos.
palco / Dijkstrafronteira / caminho
atual visitado caminho origem A → destino H
telemetria / grafo
passo00grafo carregado — origem pronta
nós visitados00estado fechado
fronteira01próximos candidatos
custo alvo—ainda calculando
playback observado · grafo
Duração que aconteceu.
Execuções concluídas nesta bancada, medidas durante o playback ativo no navegador e salvas apenas neste dispositivo.
média / últimas 0—Dijkstra · armazenamento local
sem registros ainda
Execute o algoritmo até o fim para transformar esta bancada em uma série de medições reais.
/ leitura da fronteiraDijkstra's Algorithm
Dijkstra's Algorithm
acumula evidências.
Dijkstra's Algorithm utiliza relaxamento para encontrar o menor caminho ponderado. Use quando as arestas têm custos não negativos e você quer uma distância ótima garantida.
↳
some o custo conhecido
O caminho se revela quando cada relaxamento reduz o custo conhecido.
complexidade
melhorO(E log V)
médioO(E log V)
piorO(E log V)
Complexidade do modelo com fila de prioridade, uma estrutura que escolhe o menor custo pendente. A bancada usa uma fila linear para deixar essa escolha visível; por isso, ela não é um benchmark de desempenho.
Como ler esta réguaEla não mede o tempo do seu aparelho: compara como o trabalho tende a crescer quando a rede aumenta em V (nós) e E (ligações).
operações
O(E log V) · Arestas com prioridade
O algoritmo examina arestas (E) e usa uma fila de prioridade para escolher o próximo vértice. O log V representa os níveis necessários para reorganizar essas escolhas.
Quando V dobra, cada ajuste da fila acrescenta apenas um nível; o trabalho principal ainda acompanha as arestas examinadas.comparação / duas técnicas
Compare o crescimento lado a lado
Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Comparações prontasaplique um par didático
Use este par para comparar a exploração de um grafo não ponderado com o custo adicional de priorizar caminhos de menor distância. Breadth-First Search tende a crescer mais devagar do que Dijkstra quando aumentam vértices (V) e arestas (E). Isso descreve tendência assintótica, não mede o tempo do seu aparelho.
A prioridade certifica
o menor custo pendente.
Dijkstra constrói caminhos mínimos a partir de uma origem em grafos ponderados. Em vez de escolher por ordem de descoberta, ele sempre extrai da fronteira o vértice com menor custo provisório. Sob pesos não negativos, esse custo não pode mais ser reduzido: o vértice passa de candidato a distância definitiva.
Uma rota melhor atualiza custo e predecessor.
Ao testar u → v, compare dist[u] + w(u, v) com dist[v]. Se o candidato for menor, atualize os dois registros. O predecessor guarda a rota para que o caminho possa ser reconstruído depois.
Extrair o menor rótulo torna sua distância definitiva.
Qualquer rota alternativa teria de sair da fronteira com custo igual ou maior e ainda acrescentar um peso não negativo. Por isso, nenhum caminho futuro pode reduzir a distância do vértice extraído.
/ custo, memória e implementação
O((V + E) log V) combina relações e prioridade.
Com lista de adjacência e min-heap, cada extração e atualização de prioridade custa logarítmico, resultando em O((V + E) log V). Distâncias, predecessores, estados e fila ocupam O(V) adicional. Uma implementação pode inserir uma prioridade nova e ignorar entradas antigas quando forem extraídas, dispensando um decrease-key explícito.
TRAVESSIAO((V + E) log V)Lista de adjacência e min-heap.
MEMÓRIA AUXILIARO(V)Fila e registros por vértice.
DISTÂNCIA GARANTIDAmenor custoCom pesos não negativos.
GRAFO DESCONEXOparcialVértices inalcançáveis ficam em ∞.
ESCOLHA PELO MODELO DE PESOS
“Mais curto” depende do que cada aresta significa.
Use Dijkstra para custo, tempo ou distância acumulada sem valores negativos. Se todas as arestas tiverem o mesmo custo, BFS resolve o problema com uma fila FIFO e uma garantia em número de saltos. Se a entrada puder conter pesos negativos, Bellman-Ford é a alternativa; em um ciclo negativo alcançável, não existe menor custo finito.
MODELOPRÓXIMA ESCOLHACONTRATO
BFSfila FIFOarestas de mesmo custo
Dijkstramenor custo pendentepesos não negativos
Bellman-Fordrelaxamentos por rodadaaceita pesos negativos
DECISÃO DE ENGENHARIA
Primeiro valide a semântica do peso; depois escolha a fila.
O algoritmo não decide o que “melhor” significa: ele minimiza exatamente a soma definida nas arestas. Uma rota de menor distância não minimiza automaticamente risco, emissões ou número de baldeações. Modele esses critérios no peso, preserve a não negatividade e registre predecessores quando a interface precisar explicar o trajeto, não apenas exibir seu custo.
/ por baixo do palcoPseudocódigo e
Pseudocódigo e
implementação.
A mesma rede pode ser explorada com uma fila, uma pilha ou uma função de custo. Os trechos mostram o núcleo da decisão; funções de apoio, como recuperar a rota ou escolher o menor custo, aparecem com nomes descritivos para manter o foco da explicação.
01defina distância da origem como zero
02escolha o menor custo aberto
03relaxe cada vizinho
04marque o nó como resolvido
05repita até o alvo
/ implementação sincronizada
function dijkstra(graph, start, goal) { // Relax edges from the lowest known costconst distance = { [start]: 0 };const open = [start];const settled = new Set();while (open.length) {const node = takeLowest(open, distance);if (settled.has(node)) continue;settled.add(node);if (node === goal) return distance;for (const edge of graph[node]) {const next = distance[node] + edge.weight;if (next < (distance[edge.to] ?? Infinity)) {distance[edge.to] = next; if (!open.includes(edge.to)) open.push(edge.to);}}}return distance;}