Page 43 - 4336
P. 43
вершини v визначається довжиною найкоротшого шляху, що веде
з v у х). Нехай також відомі найкоротші шляхи, що з'єднують
вершину v з виділеними m вершинами. Покажемо, як може бути
визначена m+1 найближча до v вершина.
Позначимо вершину v та m найближчих до неї вершин.
Побудуємо для кожної непозначеної вершини у шляхи, що
безпосередньо з'єднують за допомогою дуг (х, у) кожну
позначену вершину х з у. Виберемо із цих шляхів найкоротший і
будемо вважати його умовно найкоротшим шляхом з вершини v у
вершину у.
Із непозначених вершин m+1 найближчою до v вершиною є
та, для якої умовно найкоротший шлях має найменшу довжину.
Це обумовлюється тим, що найкоротший шлях з вершини v в m+1
найближчу вершину при позитивному значенні довжин усіх дуг
повинен містити в якості проміжних лише позначені вершини,
тобто вершини, що входять у число m вершин, найближчих до
вершини v.
Отже, якщо відомі m найближчих до v вершин, то m+1
найближча до v вершина може бути знайдена так, як це описано
вище. Починаючи з m=0, описана процедура може повторюватися
доти, поки не буде отриманий найкоротший шлях, що веде з
вершини v до вершини w.
4.2.1 Алгоритм Дейкстри пошуку найкоротшого шляху
Крок 1. Перед початком виконання алгоритму всі вершини
та дуги непозначені. Кожній вершині в ході виконання алгоритму
присвоюється число d(x), рівне довжині найкоротшого шляху з v
у х, що включає тільки позначені вершини.
43