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
   38   39   40   41   42   43   44   45   46   47   48