онання алгоритму дуги не пофарбовані. Кожній вершині в ході виконання алгоритму присвоюється число d (x), яка дорівнює довжині найкоротшого шляху з s в x, що включає тільки пофарбовані вершини.
Покласти d (s)=0 і d (x)=для всіх x, відмінних від s. Пофарбувати вершину s і покласти у=s (y-остання з пофарбованих вершин).
Крок 2. Для кожної неокрашенной вершини x наступним чином перерахувати величину d (x):
(1)
Якщо d (x)=для всіх нефарбованих вершин x, закінчити процедуру алгоритму: у початковому графі відсутні шляхи з вершини s у незабарвлені вершини. В іншому випадку забарвити ту з вершин x, для якої величина d (x) є найменшою. Крім того, забарвити дугу, провідну в обрану на даному кроці вершину х (для цієї дуги досягався мінімум відповідно з виразом (1)). Покласти y=x.
Крок 3. Якщо y=t, закінчити процедуру: найкоротший шлях з вершини s у вершину t знайдений (це єдиний шлях з s в t, складений з пофарбованих дуг). В іншому випадку перейти до кроку 2.
Відзначимо, що кожного разу, коли забарвлюється деяка вершина (не рахуючи вершини s), забарвлюється і деяка дуга, що заходить в дану вершину. Таким чином, на будь-якому етапі алгоритму Дейкстри в кожну вершину заходить не більше ніж одна пофарбована дуга. Крім того, пофарбовані дуги не можуть утворювати у вихідному графі цикл, так як в алгоритмі не може забарвлюватися дуга, кінцеві вершини якої вже пофарбовані. Отже, можна зробити висновок про те, що пофарбовані дуги утворюють у вихідному графі орієнтоване дерево з коренем у вершині s. Це дерево називається орієнтованим деревом найкоротших шляхів. Єдиний шлях від вершини s до будь-якої вершини x, що належить дереву найкоротших шляхів, є найкоротшим шляхом між зазначеними вершинами.
Якщо найкоротшому шляху з вершини s у вершину х в дереві найкоротших шляхів належить вершина y, то частина цього шляху, укладена між x і y, є найкоротшим шляхом між цими вершинами. Дійсно, якби між х і у існував коротший шлях, то згаданий вище шлях між вершинами s і x не можу б бути найкоротшим.
Оскільки на всіх етапах алгоритму Дейкстри пофарбовані дуги утворюють у вихідному графі орієнтоване дерево, алгоритм можна розглядати як процедуру нарощування орієнтованого дерева з коренем у вершині s. Коли в цій процедурі нарощування досягається вершина t, процедура може бути зупинена.
Якби ми хотіли визначити найкоротші шляхи з вершини s в усі вершини вихідного графа, то процедуру нарощування дерева слід було б продовжити до тих пір, поки всі вершини графа не були б включені в орієнтоване дерево найкоротших шляхів. При цьому для вихідного графа було б отримано покриває орієнтоване дерево (за умови, що в цьому графі міститься хоча б одне таке дерево). Отже, для того, щоб описаний вище алгоритм дозволяв отримувати дерево найкоротших шляхів від вершини s до всіх інших вершин, його третій крок повинен бути скоректований таким чином: якщо всі вершини виявляються забарвленими, закінчити процедуру (для будь-якої вершини x є єдиний шлях з s в x, що складається з пофарбованих дуг, і цей шлях є найкоротшим шляхом між відповідними вершинами); в іншому випадку пров?? Йти до кроку 2.
2.3 Завдання пошуку всіх найкоротших шляхів
У попередньому пункті була розглянута задача пошуку найкоротшого шляху між двома конкретними вершинами s і t. У даному розділі буде викладена завдання пош...
