Алгоритм Дейкстри. Пошук найкоротшого шляху. Побудова матриці суміжності

Державний університет «Одеська Політехніка»
Інститут комп’ютерних систем
Кафедра інформаційних систем
Розрахунково-графічна робота з дисципліни «Теорія алгоритмів»
Тема: «Алгоритм Дейкстри.Пошук найкоротшого шляху. Побудова матриці
суміжності»
Варіант 18
Виконала: студентка групи АІ-204
Зелинська Марина
Прийняли:
Арсірій О.О.
Смик С.Ю.
Одеса 2022

Завдання (Варіант 18):
Припустимо, що у Вас є список координат точок у просторі та інформація про наявність зв'язку між цими точками, побудуйте такий граф та його матрицю суміжності, реалізуйте алгоритм Дейкстри знаходження найкоротшого шляху між двома вершинами графа.
Мета: Розробка алгоритму Дейкстри для знаходження найкоротшого шляху між довільними точками у просторі, побудувати матрицю суміжності.
Опис вхідних даних:
Вершини графа, одна з яких початкова та є точкою відліку, їх кількість, ребра, відстань між вершинами.
Опис вихідних даних:
Найкоротша відстань від початкової до решти вершин, матриця суміжності алгоритму.
Загальні теоретичні відомості до алгоритму Дейкстри:
Алгоритм Дейкстри. Алгоритм голландського вченого Едсгера Дейкстри знаходить всі найкоротші шляхи з однієї наперед заданої вершини графа до всіх
інших. З його допомогою, при наявності всієї необхідної інформації, можна, наприклад, дізнатися яку послідовність доріг краще використовувати, щоб дістатися з одного міста до іншого. Мінусом даного методу є неможливість обробки графів, в яких є ребра з від’ємною вагою .

Опис досліджуваного об’єкта
Розглянемо приклад знаходження найкоротшого шляху. Дано мережу автомобільних доріг, що з'єднують зупинки міста Одеса. Деякі дороги односторонні. Знайти найкоротші шляхи від центру міста до кожного міста.
Нехай потрібно знайти найкоротші відстані від 1-ї вершини до решти.
Кружками позначені вершини, лініями – шляхи між ними (ребра графа).
Фіолетовим кольором позначені координати. Перше число - географічна широта (з округленням до цілих). Друге географічна довгота (з округленням до цілих). Географічні координати знайдені за допомогою додатку GOOGLE
MAPS.
Для розрахунку довжини ребр отриманого графа користуємося математичною формулою
|AB|² = (y2 - y1)² + (x2 - x1)²
Математичний розрахунок:
Довжина^2 від вершини 1 до 2: (46-39)^2+(30-30)^2= 49
=> Довжина 1-2: 49^0,5=7 Позначаємо на схемі (виділено блакитним)
Довжина^2 від вершини 1 до 3: (46-43)^2+(30-38)^2= 80
=> Довжина 1-3: 80^0,5≈9 Позначаємо на схемі (виділено блакитним)
Довжина^2 від вершини 1 до 6: (46-48)^2+(30-43)^2= 209

=> Довжина 1-6: 209^0,5≈14 Позначаємо на схемі (виділено блакитним).
Довжина^2 від вершини 6 до 5: (48-40)^2+(44-49)^2= 89
=> Довжина 2-4: 89^0,5≈9 Позначаємо на схемі (виділено блакитним).
Довжина^2 від вершини 2 до 3: (43-39)^2+(38-30)^2= 100
=> Довжина 2-3: 100^0,5=10 Позначаємо на схемі (виділено блакитним).
Довжина^2 від вершини 2 до 4: (35-39)^2+(46-30)^2= 270
=> Довжина 2-4: 1270^0,5≈16 Позначаємо на схемі (виділено блакитним).
Довжина^2 від вершини 3 до 4: (35-43)^2+(46-38)^2= 128
=> Довжина 2-4: 128^0,5≈11 Позначаємо на схемі (виділено блакитним).
Довжина^2 від вершини 4 до 5: (35-40)^2+(46-49)^2= 36
=> Довжина 2-4: 36^0,5=6 Позначаємо на схемі (виділено блакитним).
Довжина^2 від вершини 3 до 6: (48-46)^2+(44-42)^2= 4
=> Довжина 2-4: 4^0,5=2 Позначаємо на схемі (виділено блакитним).
Програмна реалізація знаходження довжини дороги java:
import java.util.Scanner;
import static java.lang.Math.sqrt;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Введіть координати першої зупинки: ");
System.out.println(" x1= ");
int x1 = scan.nextInt();
System.out.print(" y1= ");
int y1 = scan.nextInt();
System.out.println("Введіть координати другої зупинки: ");
System.out.println(" x2= ");
int x2 = scan.nextInt();
System.out.print(" y2= ");
int y2 = scan.nextInt();
int length = (int) sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
System.out.println("Довжина між цими зупинками = ");
System.out.println(length);
}
}

Приклад знаходження довжини дороги за допомогою програми для перевірки:
Псевдокод алгоритму
Псевдокод:
Dijkstra(G, s)
Initialize(Q) // Ініціалізація порожньої черги for (Для кожної вершини v
∊ V) do dv ←∞; pv
← NULL
Insert(Q,v,dv) // Ініціалізація пріоритету вершини у черзі Q ds←0; // Присвоювання нульової відстані початковому вузлу s
Decrease(Q,s,ds) // Оновлення пріоритету s значенням ds
VT ←
∅
for i ← 0 to |V| - 1 do u* ← DeleteMin(Q) // Вибір вузла з мінімальним пріоритетом, присвоювання його u* та видалення з його черги
VT ← VT
∪{u*} // Поміщення вузла u* з мінімальним пріоритетом у множину вершин дерева for (Для) кожної вершини u з V - VT, суміжної з u*do if du* + w (u*, u) < du du
←du* + w (u*, u); pu ← u*
Decrease(Q, u du) // Оновлення пріоритету u значенням du

Графічне моделювання алгоритму
Ініціалізація
Мітка позначена червоним вершини 1 дорівнює 0, мітки інших вершин - недосяжно велике число (в ідеалі - нескінченність). Це відбиває
те, що відстані від вершини
1 до інших вершин поки невідомі. Усі вершини графа позначаються як невідвідані.
Перший крок
Мінімальну мітку має вершина 1. Її сусідами є вершини 2, 3 та 6. Обходимо сусідів вершини по черзі.
Перший сусід вершини 1 – вершина 2, оскільки довжина шляху до неї мінімальна.
Довжина шляху до неї через вершину 1 дорівнює сумі найкоротшої відстані до вершини 1 (значення її мітки) і довжини ребра, що йде з 1-ї до
2-ї, тобто 0 + 7 = 7. Це менше поточної мітки вершини 2
(10000) тому нова мітка 2-ї вершини дорівнює 7.
Другий сусід вершини 1 – вершина 3, оскільки довжина шляху до неї мінімальна. Довжина шляху до неї через вершину 1 дорівнює сумі найкоротшої
відстані до вершини 1 (значення її мітки) і довжини ребра, що йде з 1-ї до 3-ї, тобто 0 + 9 = 9. Це менше поточної мітки вершини 3 (10000) тому нова мітка 3-ї
вершини дорівнює 9.
Третій сусід вершини 1 – вершина 6, оскільки довжина шляху до неї мінімальна. Довжина шляху до неї через вершину 1 дорівнює сумі найкоротшої
відстані до вершини 1 (значення її мітки) і довжини ребра, що йде з 1-ї до 6-ї,

тобто 0 + 14 = 14. Це менше поточної мітки вершини 6 (10000) тому нова мітка
6-ї вершини дорівнює 14.
Усі сусіди вершини 1 перевірені. Поточна мінімальна відстань до вершини 1 вважається остаточною та перегляду не підлягає. Вершина 1 відзначається як відвідана (на малюнку зеленим).
Другий крок
Крок 1 алгоритму повторюється.
Знову знаходимо «найближчу» з невідвіданих вершин. Це вершина
2 з міткою 7.
Знову намагаємося зменшити мітки сусідів обраної вершини, намагаючись пройти в них через 2
вершину. Сусідами вершини 2 є вершини 1, 3 та 4.
Вершина 1 вже відвідана.
Наступний сусід вершини 2 - вершина 3, оскільки має мінімальну мітку з вершин, відзначених як не відвідані. Якщо йти в неї через 2, то довжина такого шляху дорівнюватиме 17
(7 + 10 = 17). Але поточна мітка третьої вершини дорівнює 9, а 9 < 17 тому мітка не змінюється.
Ще один сусід вершини 2 - вершина 4. Якщо йти в неї через 2-у, то довжина такого шляху дорівнюватиме 22 (7 + 15 = 22). Оскільки 22<10000, встановлюємо мітку вершини 4 є 22.
Усі сусіди вершини 2 переглянуті, позначаємо її як відвідану(зеленим).
Третій крок
Повторюємо крок алгоритму, вибравши вершину 3.
Сусідами вершини 3 є вершини
1,2,6,4. Вершини 1,2 вже відвідані.
Наступний сусід вершини 3 - вершина 6, оскільки має мінімальну мітку з вершин, відзначених як не відвідані.
Якщо йти в неї через 3, то довжина такого шляху

дорівнюватиме 11 (9 + 2 = 11). Поточна мітка третьої вершини дорівнює 14, а
14 > 11 тому мітка змінюється. Мітка набуває значення 11
Ще один сусід вершини 3 - вершина 4. Якщо йти в неї через 3-у, то довжина такого шляху дорівнюватиме 20 (9 + 11 = 20). Оскільки 20<22, встановлюємо мітку вершини 4 є 20.
Усі сусіди вершини 3 переглянуті, позначаємо її як відвідану(зеленим).
Четвертий крок
Повторюємо крок алгоритму, вибравши вершину 6.
Сусідами вершини 6 є вершини 5,3,1. Вершини 1,3 вже відвідані.
Наступний сусід вершини 3 - вершина 5, оскільки має мінімальну мітку з вершин, відзначених як не відвідані.
Якщо йти в неї через 6, то довжина такого шляху дорівнюватиме 20 (11 + 9 = 20).
Поточна мітка третьої вершини дорівнює 10000, 20<10000, тому мітка набуває значення
20.Усі сусіди вершини 6 переглянуті, позначаємо її як відвідану(зеленим).
П’ятий крок
Повторюємо крок алгоритму, вибравши вершину 4.
Сусідами вершини 4 є вершини 5,3,2. Вершини 2,3 вже відвідані.
Наступний сусід вершини 4 - вершина 5, оскільки має мінімальну мітку з вершин, відзначених як не відвідані.
Якщо йти в неї через 4, то довжина такого шляху дорівнюватиме 26 (20 + 6 =

26). Поточна мітка третьої вершини дорівнює 20, 26>20, тому мітка не змінюється.Усі сусіди вершини 4 переглянуті, позначаємо її як відвідану(зеленим).
Шостий крок
Повторюємо крок алгоритму, вибравши вершину 5.
Сусідами вершини 5 є вершини 6,4. Вершини 6,4 вже відвідані.
Усі сусіди вершини 5 переглянуті, позначаємо її як відвідану(зеленим).
Усі вершини є відвіданими (на малюнку зеленими).
Таким чином, найкоротшим шляхом з вершини 1 у вершину 5 буде шлях через вершини 1 - 3 - 6 - 5, оскільки таким шляхом ми набираємо мінімальну вагу, що дорівнює 20 (9+2+9).
Перейдемо до виведення найкоротшого шляху. Ми знаємо довжину шляху для кожної вершини і тепер будемо розглядати вершини з кінця. Розглядаємо кінцеву вершину (у нашому випадку — вершина 5), і всі вершини, з якою вона пов'язана, знаходимо довжину шляху, віднімаючи вагу відповідного ребра з

довжини шляху кінцевої вершини.
Так, вершина 5 має довжину шляху 20. Вона пов'язана з вершинами 6 та 4.
Для вершини 6 отримаємо вагу 20 - 9 = 11 (збіг).
Для вершини 4 отримаємо вагу 20 - 6 = 14 (не збігся).
Якщо в результаті ми отримаємо значення, яке збігається з довжиною
шляху вершини (в даному випадку — вершина 6), то саме з неї був
здійснений перехід у кінцеву вершину. Відмічаємо цю вершину на шуканому шляху.
Далі визначаємо ребро, через яке ми потрапили у вершину 6. І так поки що не дійдемо до початку.
Якщо в результаті такого обходу у нас на якомусь кроці збігатимуться значення для кількох вершин, то можна взяти будь-яку з них — кілька шляхів матимуть однакову довжину.
Математичне моделювання алгоритму
Запис наприклад 3(1, 6) означає, що ми йдемо з вершини 3 у вершину 1, з відстанню (вагою) – 6.
Граф
Поточна вершина Інші вершини
1(-, 0);
Мітка залишаєтся
порожньою «-»
1(-, ∞);
2(-, ∞);
3(-, ∞);
4(-, ∞);
5(-, ∞);
6(-, ∞)

Реалізація через матрицю суміжності
Для зберігання ваги графа використовується квадратна матриця. У заголовках рядків та стовпців знаходяться вершини графа. А ваги дуг графа розміщуються у внутрішніх осередках таблиці. Граф не містить петель, тому на головній діагоналі матриці містяться нульові значення. Якщо між відповідними двома вершинами не має прямого зв’язку внутрішній осередок набуває нульового значення.
1 2
3 4
5 6
1 0
7 9
0 0
14 2
7 0
10 15 0
0 3
9 10 0
11 0
2 4
0 15 11 0
6 0
5 0
0 0
6 0
9 6
14 0
2 0
9 0
Реалізація програми на мові С++:
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#define SIZE 6
int main()
{
int a[SIZE][SIZE]; // матриця зв'язків int d[SIZE]; // мінімальна відстань int v[SIZE]; // відвідані вершини int temp, minindex, min;
int begin_index = 0;
system("chcp 1251");
system("cls");
printf("\n1- відправна зупинка- Залізничний вокзал\n2- Італійський бульвар\n3-
Велика Арнаутська\n4- парк Шевченка\n5- Троїцька\n6- Старобaзарний сквер");
printf("\n_______________________________________________\n");
// Ініціалізація матриці зв'язків for (int i = 0; i {
a[i][i] = 0;
for (int j = i + 1; j printf("\nВведіть відстань у км від %d до %d: ", i + 1, j + 1);
scanf("%d", &temp);

a[i][j] = temp;
a[j][i] = temp;
}
}
printf("\n_______________________________________________\n");
// Виведення матриці зв'язків printf("\n\tВиведення матриці зв'язків\n");
for (int i = 0; i {
for (int j = 0; j printf("%5d ", a[i][j]);
printf("\n");
}
//Ініціалізація вершин і відстаней for (int i = 0; i {
d[i] = 10000;
v[i] = 1;
}
d[begin_index] = 0;
// Крок алгоритму do {
minindex = 10000;
min = 10000;
for (int i = 0; i { // Якщо вершина не обійдена і вага мінімальна if ((v[i] == 1) && (d[i] { // Переприсвоюємо значення min = d[i];
minindex = i;
}
}
// Додаємо знайдену мінімальну вагу
// до поточної ваги вершини
// і порівнюємо з поточною мінімальною вагою вершини if (minindex != 10000)
{
for (int i = 0; i {
if (a[minindex][i] > 0)
{
temp = min + a[minindex][i];
if (temp < d[i])
{
d[i] = temp;

}
}
}
v[minindex] = 0;
}
} while (minindex < 10000);
printf("\n_______________________________________________\n");
// Виведенння найкоротших відстаней до вершин printf("\nНайкоротші відстані до вершuн: \n");
int j = 1;
for (int i = 1; i printf("Найкоротша відстань від Залізничного вокзалу (1) до %5d = %5d \n" ,j,
d[i]);
j++;
}
// Відновлення шляху int ver[SIZE]; // масив відвіданих вершин int end = 4; // індекс кінцевої вершини = 5 - 1
ver[0] = end + 1; // початковий елемент - кінцева вершина int k = 1; // індекс попередньої вершини int weight = d[end]; // вага кінцевої вершини while (end != begin_index) // поки не дійшли до початкової вершини
{
for (int i = 0; i {
int temp = weight - a[i][end]; // визначаємо вагу із попередньої вершини if (temp == d[i]) // якщо вога зпівпала з розрахунковою
{ // означає що саме із цієї вершини юув здійснений перехід weight = temp; // зберігаємо нову вагу end = i; // зберігаємо пепередню вершину ver[k] = i + 1; // і заносимо її у масив k++;
}
}
}
printf("\n_______________________________________________\n");
// Виведення шляху (початкова вершина виявилась в кінці массиву із k елементів)
printf("\nВиведення накоротшого шляху до найвіддаленішої зупинки 5
(Троїцька) \n");
for (int i = k - 1; i >= 0; i--)
printf("%3d ", ver[i]);

getchar(); getchar();
return 0;
}
Пояснення:
Спершу програма виводить про відомості про нумерацію зупинок, для
подальшої легшої роботи з пошуком маршруту (рис.1)
рис.1
Програма реалізує роботу алгоритму Дейкстри для будь-якого графа з 6
вершинами. Тобто користувач власноруч має ввести відстані між
вказаними зупинками (вершинами)(рис.2)
мал . 1
рис.2
Результат роботи програми:

Після цього користувач отримує результат роботи програми: матрицю зв’язків, перелік найкоротших відстаней для кожної точки та найкоротший шлях до останньої вершини (у нашому випадку вершина 5)
Висновки з правильності реалізації програми алгоритму Дейкстри:
По закінченню роботи програми отримано ті самі значення найкоротших шляхів що й при моделюванні. Матриця зв’язків співпадає — отже програма працює коректно.
Висновки з виконання розрахунково-графічної роботи:
В процесі виконання роботи було повторено алгоритм Дейкстри для пошуку найкоротшого шляху . Я дізналася історію алгоритму, виконала графічне, математичне моделювання алгоритму, зобразила матрицю зв’язку. Зроблена програмна реалізація на мові С++. Завдяки цій роботі стало більш зрозуміло практичне застосування вивченого алгоритму. Здобуті практичні навички з програмування та моделювання.