Основні визначення
Орієнтований граф G = (V, E) складається з безлічі вершин V і безлічі дуг E. Вершини також називають вузлами. а дуги - орієнтованими ребрами. Дуга подана в вигляді впорядкованої пари вершин (v, w). де вершина v називається початком. а w - кінцем дуги.
Неорієнтовний графG = (V, E) складається з кінцевого безлічі вершин V і безлічі ребер E. На відміну від орієнтованого графа, тут кожне ребро (v, w) відповідає невпорядкованою парі вершин: якщо (v, w) - неорієнтоване ребро, то ( v, w) = (w, v).
Вершина Х називається инцидентной ребру G, якщо ребро з'єднує цю вершину з будь-якої іншої вершиною.
У задачі про найкоротший шлях нам дано орієнтований взвешанной граф G = (V, E) з речової ваговій функцією w: E R
Вага шляху p = (v0, v1. Vk) - це сума ваг ребер, що входять в цей шлях:
Вага найкоротшого шляху з u в v дорівнює, за визначенням,
Найкоротший шлях з u в v - це будь-який шлях p з u в v. для котрого
Граф називається виродженим. якщо у нього немає ребер.
Вершини називаються суміжними. якщо існує ребро, їх з'єднує.
Порожнім називається граф без ребер. Повним називається граф, в якому кожні дві вершини суміжні.
Цикл, в якому всі вершини, крім першої та останньої, попарно різні, називається простим циклом.
Граф називається зв'язковим. якщо для будь-яких двох вершин існує шлях, що з'єднує ці вершини.
Ребра негативного ваги
Іноді ваги ребер можуть бути негативними. При цьому важливо, чи є цикли негативного ваги. Якщо з вершини s можна дістатися до циклу негативного ваги, то потім можна обходити цей цикл як завгодно довго, і вага буде все зменшуватися, так що для вершин цього циклу найкоротших шляхів не існує: В такому випадку можна вважати, що вага найкоротшого шляху є - ∞.
Якщо ж циклів отріцательногов ваги немає, то будь-який цикл можна викинути не подовжені шляху. Шляхів без циклів кінцеве число, так що вага найкоротшого шляху коректно визначено.
Подання найкоротших шляхів в алгоритмі
Часто потрібно не просто підрахувати ваги найкоротших шляхів, а й знайти самі ці шляхи. Нехай G = (V, E) - заданий граф. Для кожної вершини будемо пам'ятати її попередника. Предшественіка вершини - це або інша вершина, або NIL. По завершенні роботи алгоритмів ланцюжок попередників. що починається з довільної вершини v. буде являти собою найкоротший шлях з s в v. так що, якщо ≠ NIL, процедура Print-Path (G, s, v) надрукує найкоротший шлях з s в v.
До завершення роботи алгоритмів ланцюжка, одержувані ітераціями π. не обов'язково будуть найкоротшими шляхами, але все одно можна розглянути орієнтований підграф передування Gπ = (Vπ. E π). певний так: вершини Gπ - це ті вершини G. у яких попередник відмінний від NIL, плюс вихідна вершина: Vπ = [v] ≠ NIL> s>. Ребра Gπ - це стрілки, що вказують з π [v] ≠ NIL в v. Eπ = [v], v) E. vVπ \ s >>.
Дерево найкоротших шляхів з коренем в s є орієнтований підграф G'= (V', E').
де V 'V і E' E. для якого:- V '- безліч вершин, досяжних з вершини s.
- G 'є деревом з коренем s.
- для кожного vV 'шлях з s в v в графі G' є найкоротшим шляхом з s в v в графі G.
Сайт створено в системі uCoz