O algoritmo de Dijkstra é um algoritmo de caminho mais curto para encontrar o caminho mais curto de um vértice em um grafo com arestas não negativas. O algoritmo usa uma abordagem gulosa, onde sempre escolhe o vértice não visitado com a menor distância atual para visitar em seguida. |
O algoritmo começa definindo um vértice de origem e um conjunto de todos os vértices do grafo. Cada vértice tem uma distância atual associada, que começa como infinita para todos, exceto para o vértice de origem, que tem distância zero. |
A cada iteração, o algoritmo seleciona o vértice não visitado com a menor distância atual e o marca como visitado. Em seguida, atualiza a distância atual de cada vértice vizinho do vértice atual, verificando se o caminho até esse vértice é mais curto passando pelo vértice atual. Se for, atualiza a distância atual do vértice vizinho. |