0. Вершина xн позначається 0, інші вершини вважаються непоміченими.
1. i = i +1. Позначаються індексом i все непомічені раніше вершини, в яких є дуги від помічених вершин. Якщо позначена вершина Хк, то виконується п.2. Інакше, якщо в поточному значенні індексу i виявилися поміченими будь-які вершини, то виконується п.1. Інакше робиться висновок, що шляхи з вершини Хн в Хк немає.
2. Зворотним проходом по дугам починаючи від вершини Хк виділяються ті дуги, які інцидентні виділеним вершин і різниця між вагами яких дорівнює 1.
3. При русі від вершини Хн по виділеним дуг виявляється побудовані всі найкоротші шляхи до вершини Хк.
Хвильовий алгоритм побудови найкоротшого шляху для зваженого графа
1. Вершина Хн отримує вагу V = 0, її номер вводиться в масив М номерів
вершин, що змінили вагу. Решта вершини Xi отримують вагу Vi = ∞, їх номери не
потрапляють в масив М.
2. Якщо масив M порожній, то виконується п. 3, інакше вибирається з виключенням
з нього чергова вершина Xi. і перераховуються ваги вершин, що належать результату G (Xi) вершини Xi. "Xi Î G (Xi) (Vj = min (Vj Vi + lij)). Якщо вага Vj зменшується, то номер j включається в М. Знову виконується п. 2.
3. Якщо вага Vi = ∞, то робиться висновок, що шляхи з вершини Хн до вершини Xk
немає, інакше виконується процедура виділення дуг, така ж, як в хвильовому алгоритмі
для невиваженого графа, за винятком того, що різниця ваг вершин Xi і Xj повинна дорівнювати lij.
4. Після виділення дуг будуються найкоротші шляхи, довжини яких дорівнюють Vk.
приклад