= d (s, u) + a (u, v), тощо
З позитивності довжини всіх контурів легко випливає, що створена таким чином послідовність t, v, u, ... не містить повторень і закінчується вершиною s.
Очевидно, що вона визначає (при зверненні черговості) найкоротший шлях з s в t.
Таким чином, ми отримуємо наступний алгоритм:
Алгоритм знаходження найкоротшого шляху
Дані: Відстані D [v] від фіксованої вершини s до всіх інших вершин v? V, фіксована вершина t, матриця ваг ребер, A [u, v], u, v? v.
Результати: СТЕК містить послідовність вершин, визначальну найкоротший шлях з s в t.
begin: =?; CTEK? t; v: = t; v? s do: = вершина, для якої D [v] = D [u] + A [u, v];? u;: = u.
Нехай - орієнтований граф, | V | = n, | E | = m. Якщо вибір вершини u відбувається в результаті перегляду всіх вершин, то складність нашого алгоритму - O (n2). Якщо ми переглядаємо тільки список предше [v], що містить всі вершини u, такі що u (r) v, то в цьому випадку складність буде O (m). p align="justify"> Зазначимо, що в разі позитивних ваг ребер завдання про найкоротший шлях в неорієнтованому графі легко зводиться до аналогічної задачі для деякого орієнтованого графа. З цією метою досить замінити кожне ребро {u, v} двома дугами? u, v? і? v, u?, кожна з таким же вагою, що і {u, v}.
Однак у випадку непозитивним ваг це призводить до виникнення контурів з непозитивно завдовжки.
Далі будемо завжди припускати, що G = є орієнтованим графом, | V | = n, | E | = m. З метою спрощення викладу і уникнення вироджених випадків при оцінці складності алгоритмів будемо виключати ситуації, при яких В«більшістьВ» вершин ізольовані. p align="justify"> Будемо також припускати, що ваги дуг запам'ятовуються в масиві A [u], u, v? V (A [u, v] містить вага a (u, v)). p align="justify"> Найкоротші шляхи від фіксованої вершини
Більшість відомих алгоритмів знаходження відстані між двома фіксованими вершинами s і t спирається на дії, які в загальних рисах можна представити таким чином: при даній матриці ваг дуг A [u, v], u, v? V, обчислюються деякі верхні обмеження D [v] на відстані від s до всіх вершин v ОV. Кожен раз, коли ми встановлюємо, що D [u] + A [u, v]
Процес переривається, коли подальше поліпшення жодного з обмежень неможливо. Легко можна показати, що значення кожної з змінних D [v] одно тоді d (s, v) - відстані від s до v. Зауважимо, що для того щоб визначити відстань від s до t, ми обчислюємо тут відстані від s до всіх вершин графа. Не відомий жоден алгоритм знаходження відстані між двома фіксованими вершинами, який був би істотно ефективнішим, ніж відомі алгоритми визначення відстані від фіксованої вершини до всіх інших. P...
