p>
Шляхом (або орієнтованим маршрутом) орієнтованого графа називається послідовність дуг, в якій кінцева вершина всякої дуги, відмінною від останньої, є початковою вершиною наступної.
Так, на рис. 1.2 шляхами є послідовності дуг:
а6, а5, а9, А8, а4. (1)
а1, а6, а5, а9. (2)
а1, а6, а5, а9, А10, а6, а4. (3)
Орієнтованої ланцюгом (орцепью) називається такий шлях, в якому кожна дуга використовується не більше одного разу.
Простий орцепью називається такий шлях, в якому кожна вершина використовується не більше одного разу. Наприклад, шлях (2).
Маршрут є неорієнтований двійник шляху, і це поняття розглядається в тих випадках, коли можна знехтувати спрямованістю дуг у графі. Таким чином, маршрут є послідовність ребер? 1,? 2, ...,? q, в якій кожне ребро а i, за винятком першого і останнього ребер, пов'язане з ребрами а i - 1 і а i +1 своїми кінцевими вершинами.
У графі, зображеному на рис. 1.2, є маршрутами; дві точки над символом дуги означають, що її орієнтацією нехтують, тобто дуга розглядається як неорієнтовані ребро. Також шлях або маршрут можна зображати послідовністю вершин. Наприклад, шлях (1) буде виглядати наступним чином: х 2, х 5, х 4, х 3, х 5, х 6. Іноді дуг графа приписуються числа, звані вагою, вартістю, або довжиною цієї дуги. У цьому випадку граф називається графом з зваженими дугами. А якщо вага приписується вершин графа, то тоді виходить граф з зваженими вершинами. Якщо в графі ваги приписані і дуг і вершин, то він називається просто зваженим. При розгляді шляху ? представленого послідовністю дуг (? 1,? 2, ...,? Q), за його вага приймається число l (?), рівне сумі ваг всіх дуг, що входять до ?, тобто
Алгоритм Дейкстри
Алгоритм Дейкстри будує найкоротші шляхи, що ведуть з вихідної вершини графа до решти вершин цього графа (якщо такі є).
У процесі роботи алгоритму послідовно позначаються розглянуті вершини графа. Причому вершина, позначена останньої (на даний момент) розташована ближче до вихідної вершині, ніж всі непозначених, але далі, ніж всі помічені.
Спочатку позначається вихідна вершина; наступної, очевидно, буде позначена вершина, найближча до вихідної, і суміжна з нею.
Нехай на якомусь кроці вже позначено кілька вершин. Відомі найкоротші шляхи, що ведуть з вихідної вершини до поміченим. Для кожної з непомічених вершин проробимо наступне:
. Розглянемо всі дуги, провідні з помічених вершин в одну Непомічені. Кожна така дуга є останньою дугою на шляху з вихідної вершини в цю Непомічені.
. Виберемо з цих шляхів найкоротший. А потім виберемо серед них самий короткий до всіх Непомічені вершин, і пометим вершину, до якої він веде.
Алгоритм завершиться, коли будуть помічені всі досяжні вершини.
В результаті роботи алгоритму Дейкстри будується Дерево найкоротших шляхів.
Алгоритм, реалізований у програмі
Задаються:
. Матриця ваг дуг W [i, j], ваги дуг між вершинами i та j. Матриця симетрична і позитивна. Якщо i і j не пов'язані дугою, то W [i, j]=- 1
. Початкова вершина x1
