Розробка уроку

Тема: визначення найкоротшого шляху у зваженому графі, алгоритми Дейкстри і Флойда-Уоршелла.

Мета:

Обладнання: комп'ютери зі встановленими ОС та інтерпретатором мови Ruby.

Структура уроку

  1. Організаційний момент.
  2. Актуалізація опорних знань.
  3. Інструктаж з ТБ.
  4. Вивчення нового матеріалу.
  5. Закріплення вивченого матеріалу.
  6. Підбиття підсумків уроку.
  7. Домашнє завдання.
Хід уроку

1. Організаційний момент
Привітання та знайомство з класом. Перевірка присутності учнів.

2. Актуалізація опорних знань
Дати відповіді на питання й порівняти з очікуваним.

  1. Що таке граф?

    • Граф — це множина, що складається з елементів двох типів: вершин і пар вершин (упорядкованих чи неупорядкованих). Граф може не містити жодної пари вершин, але обовязково містить вершини.

    • Упорядковану пару вершин графа називають дугою (орієнтованим ребром в англомовній літературі) і на рисунку позначають лінією зі стріл­кою (від зображення першої вершини до зображення другої). На поданні рисунком різним дугам (ребрам) відповідають різні лінії, що не містять зображень інших вершин графа.

    • Неупорядковану пару вершин графа називають ребром (неорієнтованим ребром в англомовній літературі) і на рисунку позна­чають лінією без стрілки (між зображеннями вершин пари).

  2. Які є способи подання графів? Матриця суміжності і списки суміжності.

  3. Які є способи подання списків суміжності графів? Один масив для всіх ребер або списки.

3. Вивчення нового матеріалу

Означення 1. Запровадимо такі поняття:

  1. Граф, у якому кожному ребру (кожній дузі) поставлено у відповідність певне невід'ємне число, яке називають вагою або довжиною ребра (дуги), називають зваженим графом.

  2. Довжиною шляху (машруту) у зваженому графі називають суму довжин ланок цього шляху (машруту).

Методом «від супротивного» можна довести таке твердження.

Теорема 1. Якщо v1 v2 … vj – 1 vj vj + 1 … vk – 1 vk vk + 1 … vn є найкоротшим шляхом між вершинами v1 і vn зваженого графу, то шлях vj vj + 1 ... vk – 1 vk є найкоротшим шляхом між вершинами vj і vk .

Не обмежуючи загальності міркувань, обмежимося пошуком найкоротшого шляху від вершини v1 до вершини vn з максимальним номером.

У першому алгоритмі кожній вершині vk поставимо у відповідність пару (m; vj ), де:
m — найменша з розглянутих довжин шляху від вершини v1 до вершини vk;
vj — попередня для vk вершина на такому шляху з найменшшою довжиною.
Спочатку кожній вершині поставимо у відповідність пару (+ ∞ ;0).

Алгоритм Дейкстри (Dijkstra's algorithm)

  1. Замінюємо пару v1(+ ∞ ; 0) на v1(0; 0) й оголошуємо вершину v1 сталою, а решту вершин — змінними.

  2. Після того, як вершина vk.(m; vj.) стає сталою, для кожної вершини vi, що суміжна з вершиною vk, знаходимо суму m і довжину ребра (дуги) з vk до vi. Якщо знайдена сума менша за знайдену поточну відстань від v1 до vi, то замінюємо цю поточну відстань на знайдену суму, а другу координату вершини vi — на vk.

  3. Знаходимо мінімум відстаней, приписаних змінним вершинам. Першу вершину з такою відстанню від v1 оголошуємо сталою.

  4. Якщо vn ще не оголошено сталою вершиною, то повертаємося на виконання пункту 2.

  5. Якщо vn оголошено сталою вершиною, то відстань, приписана цій вершині, є найменшою довжиною шляху від v1 до vn.

  6. Один з можливих найкоротших шляхів від v1 до vn відновлюємо «з кінця», починаючи з вершини vn, переходом до попередньої вершини найкоротшого шляху (див. другу координату пари, приписаної до кожної вершини).

Для формулювання алгоритму пошуку найкоротшого шляху у матричному вигляді скористаємося такими позначеннями для матриць-рядків:

A = (a1; a2; ... ; an),     B = (b1; b2; ... ; bn)

і числа c:

A + B = (a1 + b1; a2 + b2; ... ; an + bn);

min(A, B) = (min(a1, b1); min(a2, b2); ... ; min(an, bn));

A + c = с + A = (a1 + c; a2 + c; ... ; an + c).

У наступному алгоритмі скористаємося такими позначеннями:

W — матриця, що має n рядків і n стовпчиків;

W.(i, j.) — елемент такої матриці, розташований у i-му рядку й j-му стовпчику. Цей елемент дорівнює відстані від вершини vi до вершини vj для суміжних вершин та +∞ в іншому випадку, W.(j, j.) = 0;

W.(j.) — j-ий рядок матриці W;

Pr.(j.) — елемент матриці-рядка Pr — дорівнює номеру вершини, що беспосередньо передує вершині vj на найкоротшому шляху від v1;

P.(j.) — елемент матриці-рядка P, що дорівнює справжній найменшій відстані від вершини v1 до vj.;

T.(j.) — елемент матриці-рядка T, що дорівнює поточній найменшій (серед розглянутих) відстані від вершини v1 до vj.;

V — номер вершини, яку оголошеною сталою останньою;

S — матриця-рядок для зберігання суми P.(V.) + W.(V.).

Тут всі матриці-рядки мають n елементів.

Алгоритм Дейкстри у матричному поданні

  1. Надати таких значень: V = 1; P.(1) = 0; T.(1) = + ∞ ; W.(j, 1) = + ∞ при 1 ≤ j ≤ n (вершину 1 оголошено сталою).

  2. Здійснити такі дії:
    • знайти S = P.(V.) + W.(V.);
    • при 1 ≤ j ≤ n, якщо S.(j.) < T.(j.), надати значення Pr.(j.) = V;
    • замінити поточне значення T на min(T, S.);
    • визначити i, при якому T.(i.) = min{ T.(j.) | 1 ≤ j ≤ n};
    • надати таких значень: V = i; P.(i.) = T.(i.), T.(i.) = +∞ ; W.(j, i.) = + ∞ при 1 ≤ j ≤ n.

  3. Якщо i відмінне від n, то повернутися на виконання пункту 2.

  4. Якщо i = n, то P.(i.) є найменшою довжиною шляху від v1 до vn.

  5. Один з можливих найкоротших шляхів від v1 до vn відновлюємо «з кінця», починаючи з вершини vn, переходом до попередньої вершини найкоротшого шляху (за елементами матриці-рядка Pr).

На початку виконання наступного алгоритму зміст елементів матриці W такий самий, що й у попередньому алгоритмі. Алгоритм полягає у перетворенні матриці W з метою заміни елементів, що спочатку дорівнюють +∞ , на довжини найкоротших маршрутів з кількістю ланок до 2, 3, ... (n – 1), що проходять через вершини v1, v2, ... , vn .

Алгоритм Флойда-Уоршолла (Floyd-Warshall algorithm)
порівнює всі можливі шляхи у графі між кожною парою вершин:
змінюючи k від 1 до n включно,
змінюючи i від 1 до n включно,
змінюючи j від 1 до n включно:
замінити W.(i, j.) на min(W.(i, j.), W.(i, k.) + W.(k, j.)).

Таким чином за O(|n|3) порівнянь буде поступово поліпшено оцінки щодо найкорот­шого шляху між двома вершинами, поки оцінка не стає оптимальною.

4. Інструктаж з ТБ
5. Вироблення практичних навичок

Завдання 1. Вершини неорієнтованого зваженого графа занумеровано послідовними невід'ємними цілими числами, починаючи з 0. Подавши структуру графа списками суміжності, створити програму знаходження згідно з алгоритмом Дейкстри найкоротшого шляху між вершинами з найменшим і найбільшим номерами.

Вхідні дані. Перший рядок вхідного файлу містить два числа: кількість вершин і кількість ребер графа. Кожний з наступних рядків містять по два номери вершин, сполучених ребром, і вагу цього ребра. Таким чином кожне ребро графа згадано один раз.

Вихідні дані. Перший рядок вихідного файлу має містити шукану довжину найкоротшого маршруту. У другому рядку потрібно вивести номери послідовних вершин найкоротшого маршруту від вершини з найбільшим номером до вершини з найменшим номером 0.

Наприклад, для графа, що має 7 вершин і 8 ребер:

❺—③—❷—⑨—❸
| | |⋱
① ⑦ ⑤ ⑨
| | | ⋱
❹—②—⓿ ❶—③—❻

(тут номери вершин подано білими цифрами у чорних кругах, ваги ребер — чорними цифрами всередині кіл) файл вхідних даних може мати такий вигляд:

7 8
0 2 7
0 4 2
1 3 5
1 6 3
2 3 9
2 5 3
3 6 9
4 5 1

Вихідний файл у цьому випадку повинен містити таке:

23
6 1 3 2 5 4 0

 Зберегти файл програми у теці з назвою Ваше_прізвище_1 у вказаному вчителем місці. Порівняти створену програму з демонстра­ційним розв'я­занням.

6. Підбиття підсумків уроку
Виставлення оцінок.

7. Домашнє завдання
Вивчити матеріал уроку. Вершини неорієнтованого зваженого графа занумеровано послідовними натуральними числами, починаючи з 1. Подавши структуру графа матрицею суміжності, створити програму знаходження згідно з алгоритмом Флойда-Уоршолла найкоротшого шляху між вершинами з найменшим і найбільшим номерами. Вимоги до вхідних і вихідних даних такі самі, як у завданні 1 класної роботи.

Текст упорядкував Олександр Рудик.