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