Алгоритмическое обеспечение

Рассмотрим изложенный метод на конкретном примере, а именно: определим кратчайший путь из вершины 1 в вершину 6 для неориентированной сети, показанной на рисунке 1.

Рисунок 1 - Неориентированная сеть с заданными длинами дуг для нахождения кратчайшего пути

На предварительном этапе вершина 1 отмечается числом m1 = 0, а модифицированные длины совпадают с заданными длинами дуг.

Итерация 1. Так как из вершины 1 не выходят дуги нулевой длины, дальнейшая отметка вершин невозможна. Переходим к этапу 2. Смежными с вершиной 1 являются вершины 2 и 3. Для них определяем ∆ = min{1,2, 1,3}=2 и вычитаем ее из 1,2, 1,3. После преобразования имеем 1,2 = 0, 1,3 = 1. Результаты можно увидеть на рисунке 2.

Рисунок 2 - Измененная сеть после выполнения первой итерации

Итерация 2. Помечаем вершину 2 m2 = 1 (см. рисунок 3). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с помеченными вершинами 1 и 2 являются вершины 3,4,5. Из чего определяем ∆ = min{1,3, 2,3, 2,4, 2,5}=1 и после соответствующего преобразования имеем

Рисунок 3 - Измененная сеть после выполнения второй итерации

Итерация 3. В вершину 3 ведут дуги нулевой длины как из вершины 1, так и из вершины 2. Поскольку выбор здесь может быть произвольным, пометим вершину 3 числом m3 = 1 (рисунок 4). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее отмеченными вершинами являются вершины 4,5. Из чего определяем ∆ = min{2,4, 2,5, 3,4, 3,5}=1 и после преобразования имеем 2,5 = 8, 2,4 = 0, 3,5 = 3, 3,4 = 5.

Рисунок 4 - Измененная сеть после выполнения третей итерации

Итерация 4. Помечаем вершину 4 m4 =2 (рисунок 5). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежными с ранее помеченными вершинами являются вершины 5,6. Из чего определяем ∆ = min{2,5, 3,5, 4,5, 4,6}=3 и после преобразования имеем 2,5 = 5, 3,5 = 0, 4,5 = 0, 4,6 =5.

Рисунок 5 - Измененная сеть после выполнения четвертой итерации

Итерация 5. В вершину 5 ведут дуги нулевой длины как из вершины 3, так и из вершины 4. Руководствуясь теми же соображениями, что и на итерации 3, пометим вершину 5 числом m5 =3 (рисунок 6). Дальнейшая пометка невозможна, поэтому переходим к этапу 2. Смежной с ранее отмеченными вершинами является вершина 6. Из чего определяем ∆ = min{4,6, 5,6}=2 и после преобразования имеем 4,6 = 3, 5,6 = 0.