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

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

Итерация 6. В вершину 6 ведет дуга нулевой длины из вершины 5, поэтому помечаем ее числом m6=5 (рисунок 7). Поскольку мы отметили конечную вершину маршрута, то алгоритм завершен и мы можем, используя значения отметок для родителей, выписать искомый кратчайший путь (1, 3, 5, 6).

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

Следует также добавить, что если бы наш выбор на итерациях 3 и 5 был иным, то мы получили бы альтернативный путь той же длины (1, 2, 4, 5, 6), т. е. рассмотренная задача имеет несколько решений.

Программное обеспечение