Тема заняття "Теорія графів. Алгоритм Дейкстри".
Алгоритм Дейкстри
Цей алгоритм для розв’язання задачі знаходження найкоротших маршрутів на карті був запропонований Дейкстрой (E.W. Dijkstra) у 1959 році.
Алгоритм дозволяє знайти розв’язок задачі про найкоротші шляхи у зваженому графі від визначеної вершини до всіх інших за умови, що вага ребер невід’ємна. Ідея алгоритму полягає в тому, щоб прокладати маршрути через проміжні вершини, обираючи на кожному кроці найкоротші доступні ребра графа.
Введемо позначення для детального опису алгоритму. Вершину, для якої шукаємо шляхи до всіх інших, назвемо стартовою (її номер позначимо St). Алгоритм використовує три масиви з n чисел кожний (n – кількість вершин графа). Перший масив містить мітки з двома значеннями: 0 – вершина ще не розглянута, і 1 – вершина вже розглянута. Назвемо цей масив Lbl. Другий масив містить значення найкоротших на момент перегляду відстаней від кожної вершини графа до стартової вершини. Позначимо цей масив Dist. Третій масив містить номери вершин, відвідування яких дозволяє скоротити довжину шляху від стартової вершини Vst до поточної (попередники на шляху до поточної вершини). Ім’я третього масиву – Path. Матриця відстаней D задає довжини ребер у графі; якщо між вершинами з номерами і та k прямої дуги немає, то D[і, k] містить число, умовно рівне "машинній нескінченності".
У першому наближенні вважаємо за найкоротші шляхи від стартової вершини до всіх інших прямий шлях, довжина якого зазначена у матриці відстаней. Значення цих відстаней заносимо до масиву Dist, а номер стартової вершини – до масиву Path.
Далі намагаємось скоротити відстані, обираючи шлях через інші вершини замість прямого. Вибір проміжних вершин здійснюємо "жадібним" методом. Для цього знаходимо вершину, шлях до якої на даному кроці найкоротший (найменше значення в масиві Dist), але спроби обрати її за проміжну ще не виконувалось (відповідне їй значення в масиві Lbl дорівнює 0; замінюємо його на 1). Для кожної вершини обчислюємо довжину шляху через обрану проміжну вершину. Якщо отримана відстань скорочує шлях до стартової вершини, заносимо її до відповідного елемента масиву Dist, а номер проміжної вершини – до масиву Path. Спробу скоротити відстань повторюємо, доки не розглянемо в ролі проміжних усі вершини графа.
Для відновлення номерів вершин у найкоротших шляхах використовуємо дані з масиву Path.
Порядок виконання алгоритму наступний.
1. Ініціалізація.
У циклі від 1 до n заповнюємо нулями масив Lbl.
Заповнюємо масив Path номером стартової вершини St.
Переносимо рядок з індексом St матриці D до масиву Dist.
Lbl [St] = 1; Path [St] = 0;
2. Визначення довжини шляхів.
Повторимо n – 2 рази операцію уточнення маршруту:
2.1. Знаходимо мінімальну з відстаней до неопрацьованих вершин (тобто тих j, для яких Lbl [j] = 0; j = 1, …, n). Припустимо, що мінімум знаходиться під індексом k.
2.2. Помічаємо вершину k як опрацьовану: Lbl [k] = 1;
2.3. Для всіх неопрацьованих вершин, тобто для всіх j від 1 до n, таких що Lbl [j] = 0:
Якщо Dist [j] > Dist [k] + D [j, k], то Dist [j] = Dist [k] + D [j, k]; Path [j] = k.
Умова означає, що шлях від стартової вершии Vst до поточної Vj довший, ніж шлях через проміжну вершину: від Vst до Vk плюс шлях від Vk до Vj.
Після виконання n – 2 ітерацій масив Dist міститиме остаточні довжини шляхів від стартової вершини до всіх інших.
3. Тепер треба назвати всі вершини, що входять до найкоротшого маршруту.
Шлях від стартової вершини Vst до будь-якої зазначеної Vj виводиться у зворотному напрямку наступним чином.
3.1. Z = Path[j];
3.2. Вивести Z;
3.3. Z = Path[Z]. Якщо Z = 0, то виведення маршруту завершено, в іншому разі перейти до 3.2.
Виконання алгоритму завершено.
Алгоритму в даній реалізації потрібно n – 2 разів переглянути масив Dist з n елементів, тобто алгоритм Дейкстри має квадратичну складність: O(n2).
Алгоритм дозволяє знайти розв’язок задачі про найкоротші шляхи у зваженому графі від визначеної вершини до всіх інших за умови, що вага ребер невід’ємна. Ідея алгоритму полягає в тому, щоб прокладати маршрути через проміжні вершини, обираючи на кожному кроці найкоротші доступні ребра графа.
Введемо позначення для детального опису алгоритму. Вершину, для якої шукаємо шляхи до всіх інших, назвемо стартовою (її номер позначимо St). Алгоритм використовує три масиви з n чисел кожний (n – кількість вершин графа). Перший масив містить мітки з двома значеннями: 0 – вершина ще не розглянута, і 1 – вершина вже розглянута. Назвемо цей масив Lbl. Другий масив містить значення найкоротших на момент перегляду відстаней від кожної вершини графа до стартової вершини. Позначимо цей масив Dist. Третій масив містить номери вершин, відвідування яких дозволяє скоротити довжину шляху від стартової вершини Vst до поточної (попередники на шляху до поточної вершини). Ім’я третього масиву – Path. Матриця відстаней D задає довжини ребер у графі; якщо між вершинами з номерами і та k прямої дуги немає, то D[і, k] містить число, умовно рівне "машинній нескінченності".
У першому наближенні вважаємо за найкоротші шляхи від стартової вершини до всіх інших прямий шлях, довжина якого зазначена у матриці відстаней. Значення цих відстаней заносимо до масиву Dist, а номер стартової вершини – до масиву Path.
Далі намагаємось скоротити відстані, обираючи шлях через інші вершини замість прямого. Вибір проміжних вершин здійснюємо "жадібним" методом. Для цього знаходимо вершину, шлях до якої на даному кроці найкоротший (найменше значення в масиві Dist), але спроби обрати її за проміжну ще не виконувалось (відповідне їй значення в масиві Lbl дорівнює 0; замінюємо його на 1). Для кожної вершини обчислюємо довжину шляху через обрану проміжну вершину. Якщо отримана відстань скорочує шлях до стартової вершини, заносимо її до відповідного елемента масиву Dist, а номер проміжної вершини – до масиву Path. Спробу скоротити відстань повторюємо, доки не розглянемо в ролі проміжних усі вершини графа.
Для відновлення номерів вершин у найкоротших шляхах використовуємо дані з масиву Path.
Порядок виконання алгоритму наступний.
1. Ініціалізація.
У циклі від 1 до n заповнюємо нулями масив Lbl.
Заповнюємо масив Path номером стартової вершини St.
Переносимо рядок з індексом St матриці D до масиву Dist.
Lbl [St] = 1; Path [St] = 0;
2. Визначення довжини шляхів.
Повторимо n – 2 рази операцію уточнення маршруту:
2.1. Знаходимо мінімальну з відстаней до неопрацьованих вершин (тобто тих j, для яких Lbl [j] = 0; j = 1, …, n). Припустимо, що мінімум знаходиться під індексом k.
2.2. Помічаємо вершину k як опрацьовану: Lbl [k] = 1;
2.3. Для всіх неопрацьованих вершин, тобто для всіх j від 1 до n, таких що Lbl [j] = 0:
Якщо Dist [j] > Dist [k] + D [j, k], то Dist [j] = Dist [k] + D [j, k]; Path [j] = k.
Умова означає, що шлях від стартової вершии Vst до поточної Vj довший, ніж шлях через проміжну вершину: від Vst до Vk плюс шлях від Vk до Vj.
Після виконання n – 2 ітерацій масив Dist міститиме остаточні довжини шляхів від стартової вершини до всіх інших.
3. Тепер треба назвати всі вершини, що входять до найкоротшого маршруту.
Шлях від стартової вершини Vst до будь-якої зазначеної Vj виводиться у зворотному напрямку наступним чином.
3.1. Z = Path[j];
3.2. Вивести Z;
3.3. Z = Path[Z]. Якщо Z = 0, то виведення маршруту завершено, в іншому разі перейти до 3.2.
Виконання алгоритму завершено.
Алгоритму в даній реалізації потрібно n – 2 разів переглянути масив Dist з n елементів, тобто алгоритм Дейкстри має квадратичну складність: O(n2).
