Dijkstra.
Escolha o custo conhecido mais baixo e relaxe o mapa.
Encontra o menor caminho em grafos com pesos positivos.
Duração que aconteceu.
Execuções concluídas nesta bancada, medidas durante o playback ativo no navegador e salvas apenas neste dispositivo.
Execute o algoritmo até o fim para transformar esta bancada em uma série de medições reais.
Dijkstra
acumula evidências.
Dijkstra utiliza para encontrar o menor caminho ponderado. Use quando as arestas têm custos positivos e você quer uma distância ótima garantida.
some o custo conhecido
O caminho se revela quando cada reduz o custo conhecido.
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.
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.
function dijkstra(graph, start, goal) {const distance = { [start]: 0 };const open = [start];while (open.length) {const node = takeLowest(open, distance);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; open.push(edge.to);}}}return distance;}