Page 43 - 4336

вершини 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