ює s . На черговому ж кроці ми намагаємося поліпшити довжину шляху до кожної з вершин другої множини, порівнюючи вирази l [p] + a (p, i) і l [i]. Потрібно показати, чому мінімальне зі значень l, розглянутих на поточному кроці, є довжиною найкоротшого шляху до відповідної вершини, а, отже, цей шлях містить тільки вершини з першого безлічі. Якщо це не так, тобто найкоротший шлях до цієї вершини містить і вершини з другої множини, то мінімальної виявилася б довжина шляху від s до однієї з цих вершин. Значить найкоротший шлях до вершини p проходить тільки через вершини першої множини і більше його перераховуватися не потрібно.
Наведемо схему програми, що реалізує цей алгоритм (функцію a (i, j) і значення "нескінченності" визначати не будемо):
for i: = 1 to nn do
begin
l [i] = ВҐ;
b [i]: = false
end;
p: = s; l [s]: = 0;
b [s]: = true;
f: = true; {cтоит чи шукати далі}
while (p <> t) and f do
begin
f: = false;
for i: = 1 to nn do
if not b [i] then
if l [p] + a (p, i)
min: = t; {важливо, що b [t] = false}
for i: = 1 to n do
if (not b [i]) and (l [i]
if l [min] <ВҐ then
begin
p: = min; b [p]: = true; f: = true
end
end;
Нескладно підрахувати, що трудомісткість алгоритму становить O ( N 2 ), що окупає деякі складнощі в його реалізації. Як і у випадку застосування "Хвильового" алгоритму в невиважені графі, асимптотична оцінка не зміниться якщо нам буде потрібно підрахувати довжину шляху від s до кожної з вершин графа. Тому, як і в алгоритмі Флойда, довжини найкоротших шляхів між усіма парами вершин можуть бути розраховані за O ( N 3 ) операцій.
Висновок
Отже, неформально, граф можна визначити як набір вершин (міста, перехрестя, комп'ютери, літери, цифри кістки доміно, мікросхеми, люди) і зв'язків між ними: дороги між містами; вулиці між перехрестями; провідні лінії зв'язку між комп'ютерами; слова, що починаються на одну букву і закачується на іншу або цю ж літеру; провідники, що з'єднують мікросхеми; родинні стосунки, наприклад, Олексій - син Петра. Двонаправлені зв'язку, наприклад, дороги з двостороннім рухом, прийнято називати ребрами графа; а односпрямовані зв'язку, наприклад, дороги з одностороннім рухом, прийнято називати дугами графа. Граф, у якому вершини з'єднуються ребрами, прийнято називати неорієнтованим графом, а граф, в якому хоча б деякі вершини з'єднуються дугами, прийнято називати орієнтованим графом.
Література
1. Андрєєва Є., Фаліна І. Системи числення та комп'ютерна арифметика. М.: Лабораторія базових знань, 2000.
2. Станкевич А . С. Рішення завдань I Всеросійської командної олімпіади з програмування. "Інформатика", № 12, 2001. p> 3. Окулов С.М. 100 завдань з інформатики. Кіров: вид-во ВДПУ, 2000. p> 4. Андрєєва Є.В. Рішення завдань XIII Всеросійської олімпіади з інформатики. "Інформатика", № 19, 2001. p> 5. Ахо А.А., Хопкрофта Д.Е., Ульман Д.Д. Структури даних і алгоритми. М.: "Вільямс", 2000. p> 6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритми. Побудова та аналіз. М.: МЦНМО, 2000. p> 7. Липський В. Комбінаторика для програмістів. М.: "Світ", 1988. p> 8. Вірт Н. Алгоритми та структури даних. Санкт-Петербург: "Невський діалект", 2001. br/>
