bel (s)=0, perm (s)=1 і pred (s)=s. Для всіх v <> s покласти label (v) =?, perm (v)=0, pred (v)=v.
. Нехай i=0 і u=s . ( u - остання з вершин з незмінною міткою. Тепер - це вершина s .)
. (Обчислення label і зміна елементів масиву pred ). Покласти i=i + 1 . Виконати для кожної вершини, крім вершин з незмінною міткою, наступні дії: 1) Покласти M=min {label (v), label (u) + w (u, v)}. 2) Якщо M то покласти label (v)=M і pred (v)=u.
. (Виділення вершин u i . ) Серед усіх вершин, що не позначені незмінною міткою, знайти вершину w з найменшою міткою. (Якщо таких вершин кілька, то вибір можна зробити довільно.) Покласти perm (w)=1 і u i =w ( u i =w, і вона є останньою вершиною з незмінною міткою.)
. Якщо i < n - 1, то йти до кроку 3. Інакше halt . (Усі найкоротші шляхи знайдені). Мітки вершин являють собою довжини найкоротших шляхів. v, pred (v), pred (pred (v)), ..., s є вершини найкоротшого орієнтованого sv - шляху.
Тут label - це масив, в якому зберігаються поточні мітки вершин. Вершини стають постійно поміченими, коли вони виявляються рівними u i для будь-якого i. Ми використовуємо масив perm, щоб вказати, які вершини постійно помічені. Якщо perm (v)=1, то v є постійно поміченої вершиною. Відзначимо, що в такому випадку мітка v дорівнює d (s, v). Спочатку perm (s)=1 і perm (v)=0 для всіх v <> s.
Pred - масив покажчиків на вершини, з яких здійснено перехід в вершини з незмінною міткою, то v, pred (v), pred ( pred (v)), ..., s є вершини, складові найкоротший орієнтований шлях з s в v.
Даний алгоритм працює також для вирішення завдання комівояжера.
Завдання комівояжера
Завдання комівояжера (англ. Travelling salesman problem, TSP) (комівояжер - мандрівний торговець) - одна з найвідоміших задач комбінаторної оптимізації, що полягає у знаходженні самого вигідного маршруту, що проходить через вказані міста хоча б по одному разу з наступним поверненням у вихідний місто. В умовах задачі вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості і тому подібного. Як правило, вказується, що маршру...
