Page 45 - 4336

належить дереву найкоротших шляхів, є найкоротшим шляхом

між зазначеними вершинами.

Якщо найкоротшому шляху з вершини v у вершину х у

дереві найкоротших шляхів належить вершина у, то частина

цього шляху, що знаходиться між у та х, є найкоротшим шляхом

між цими вершинами.

Оскільки на всіх етапах алгоритму Дейкстри позначені дуги

утворюють у вихідному графі орієнтоване дерево, алгоритм

можна розглядати як процедуру нарощування орієнтованого

дерева з коренем у вершині v. Коли в даній процедурі

нарощування досягається вершина w, то вона може бути

зупинена.

Якщо необхідно було б визначити найкоротші шляхи з

вершини v в усі вершини вхідного графа, то процедуру

нарощування дерева варто було б продовжити доти, поки всі

вершини графа не були б включені в орієнтоване дерево

найкоротших шляхів. При цьому, для вхідного графа було б

отримане кістякове орієнтоване дерево (за умови, що в даному

графі існує хоча б одне таке дерево). Отже, для того, щоб

описаний вище алгоритм дозволяв одержувати дерево

найкоротших шляхів від вершини v до усіх інших вершин, його

третій крок повинен бути скорегований у такий спосіб: якщо всі

вершини виявляються позначеними, закінчити процедуру (для

будь-якої вершини х є єдиний шлях з v в х, що складається із

позначених дуг, і цей шлях є найкоротшим шляхом між

відповідними вершинами); в іншому випадку перейти до кроку 2.

Приклад 4.2. Застосувати алгоритм Дейкстри до графа,

зображеного на рис. 4.3, для знаходження в ньому найкоротшого

шляху між вершинами v та w.

45