Алгоритм працює покроково на кожному кроці він «відвідує» одну вершину і намагається зменшувати мітки. Робота алгоритму завершується коли всі вершини відвідані. Ініціалізація. Мітка самої вершини a належить рівною 0, мітки інших вершин – нескінченності.
Алгоритм Дейкстри (Dijkstra's algorithm) [1, 2] – алгоритм на графах, винайдений нідерландським ученим Е. Дейксті рій у 1959 році. Алгоритм дозволяє знаходити найкоротшу відстань від однієї з вершин графа до решти.
Складність алгоритму У гіршому випадку, кожне ребро призводить до зміни одного елемента структури, тобто O(E) змін. Якщо вершини зберігаються у простому масиві та для пошуку мінімуму використовується алгоритм лінійного пошуку, тимчасова складність алгоритму Дейкстри становить O(V * V + E) = O(V²).
Опис алгоритму A* покроково переглядає всі шляхи, що ведуть від початкової вершини до кінцевої, поки не знайде мінімальний. Як і всі поінформовані алгоритми пошуку, він спочатку переглядає ті маршрути, які «здаються» провідними до мети.