Дана задача полягає в знаходженні зв’язаних доріг на транспортній мережі, які в сукупності мають мінімальну довжину від вихідного пункту до пункту призначення.
Приклад 2.2. На рис. 2.7 задана мережа, в якій вузол 1 – це початкова точка (вихідний пункт), а вузол 7 – кінцева точка (пункт призначення).
Рис. 2.7.
Потрібно знайти найкоротший шлях з пункту 1 в пункт 7 і його довжину.
Розв’язок. Позначимо через — відстань на мережі між суміжними вузлами і та j, — найкоротшу відстань між першим та j-им вузлом. Процедура знаходження найкоротшого шляху завершиться тоді, коли буде знайдено . Для знаходження використовуємо формулу .
Проведемо поетапне знаходження :
.
Мінімальна відстань між вузлами 1 і 7 дорівнює 13, а відповідний маршрут 1→2→5→7.