Урок 13                                                                                     Інформатика 11 (АП)

Алгоритм Флойда-Уоршелла

Мета.

Навчальна. Ознайомити з способами визначення найкоротшого шляху в графі, алгоритмом Флойда-Уоршелла.

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

Виховна. Виховувати наполегливість, естетичність у оформленні, грамотно висловлювати свої думки.

Тип уроку. Засвоєння нових знань і навичок.

Матеріали для роботи з учнями:

Інформатика: Методи побудови алгоритмів та їх аналіз. Oбчисл. алгоритми: Навч. посіб. для 9-10 кл із поглибл. вивч. інформатики. - К.: Генеза, 2009.

Мультимедійне обладнання.

Основні поняття теорії графів

Теорія графів

План

• Організація класу.
• Мотивація навчальної діяльност.
• Структури даних: проста змінна, масив, стек.
• Практичні завдання.
• Типові запитання до уроку.
• Домашнє завдання.

Пам’ятка для учня!

• Пригадайте правила техніки безпеки при роботі з ПК.
• Через кожні 15 хв. виконуйте вправи для очей та для зняття м’язової втоми.

Хід уроку

1. Організаційний момент.

2. Актуалізація опорних знань.

        Фронтальне опитування тестування.

3. Мотивація навчальної діяльності.

Логічно запитати: а як визначити найкоротший шлях між двома вершинами такого графа? Саме таку задачу ми зараз і розв’яжемо. У цього алго­ритму, який призначений для розв’язання поставленої задачі, є автор - відомий голландський учений, спеціаліст в царині комп’ютерних наук, один із класиків програмування, алгоритміст Едсгер Дейкстра (1930-2002).

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

Алгоритм Флойда-Уоршелла

З  алгоритму Дейкстри зрозуміло, що можна знайти найкоротшу відстань від заданої вершини графа до решти його вер­шин. А якщо ця інформація потрібна для будь-якої вершини графа? Найперша відповідь, яка спадає на думку: необхідно виконати алгоритм Дейкстри в циклі для всіх вершин графа. І це вірно. Питання лише в часі виконання такого алгоритму, оскіль­ки його оцінка буде O(n3). Однак існує компактніший за записом алгоритм Флойда-Уоршелла, з яким ми зараз і ознайомимося.

Уявімо собі, що до вершин заданого графа прив’язано гумову мотузку. Спочатку будемо вважати, що відстанню між вершина­ми і та j є довжина цієї мотузки. Але якщо ми її розтягнемо і за­чепимо за вершину k, то тепер відстань між вершинами і та j можна вирахувати як суму довжин між вершинами і, k та k, j.

Якщо ця сумарна відстань через вершину виявиться меншою, то надалі необхідно враховувати саме її. Отже, ми отримали ту са­му формулу, що і в алгоритмі Дейкстри: di,j = min(di,j, di,k + dk,j).

А тепер запишемо сам алгоритм:

1. Визначити вершину графа к = 1, через яку буде здійсню­ватися перерахунок відстані між вершинами і та j.
2. Визначити вершину і = 1.
3. Визначити вершину j = 1.
4. Якщо величина di,k + dk,j  менша за значення di,j, то замінити значення di,j  на di,k +dk,j. В іншому разі залишити зна­чення di,j без змін.
5. Якщо j <=n, то перейти до наступної вершини j + 1 і повер­нутися до п. 4.
6. Якщо і <=n, то перейти до наступної вершини і + 1 і повер­нутися до п. 3.
7. Якщо к<=n, то перейти до наступної вершини к + 1 і повер­нутися до п. 2.
8. Завершити алгоритм.

У результаті виконання алгоритму елементи di,j будуть міс­тити найкоротшу відстань між відповідними вершинами графа і та j.

Реалізація алгоритму Флойда-Уоршелла мовою Равсаі буде такою:

Як бачимо, алгоритм найпростіший як у розумінні, так і в його реалізації. Єдине, що слід обов’язково зазначити, це те, що за даним алгоритмом не можна визначити шлях між вершина­ми і та j, який дає визначений найкращий результат. Тому, як­що умова задачі вимагає цієї інформації, то слід все-таки засто­сувати алгоритм Дейкстри для кожної вершини заданого графа.

Завершимо ознайомлення з алгоритмом Флойда-Уоршелла однією практичною порадою. Під час реалізації алгоритму у вигляді програми слід підібрати таке значення елементів d[і,j], що відповідає поняттю «безмежність», тобто відсутність ребра між вершинами і та j.

Нагадаємо оцінку алгоритму Флойда-Уоршелла, яка була дана на початку. Вона становить O(n3) і визначається за кіль­кістю вкладених циклів, що реалізують описаний алгоритм.

Для тестування алгоритму Флойда-Уоршелла можна ви­користати ті самі тести, що й для алгоритму Дейкстри. Це дасть змогу перевірити коректність роботи обох алгоритмів.

5. Завдання для виконання

1. Розробити та реалізувати у вигляді програми алгоритм Флойда-Уоршелла для заданого графа.
2. Виконати завдання 5 для зваженого неорієнтованого графа з кількістю вершин N <= 10. Результат виконання програми вивести у файл.
3. Виконати завдання 5 для зваженого орієнтованого графа з кількістю вершин N <= 10. Результат виконання програми вивести у файл.
4. Виконати завдання 6-7 для графа з кількістю вершин N = 100. Результат виконання програми вивести у файл.

6. Питання до уроку.

1. Яку задачу призначений розв’язувати алгоритм Флойда-Уор­шелла?
2. Якою є оцінка виконання алгоритму Флойда-Уоршелла? Обґрунтуйте свою відповідь.
3. Сформулюйте і запишіть алгоритм Флойда-Уоршелла.
4. Яким чином реалізується алгоритм Флойда-Уоршелла мовою РавсаІ? Запишіть фрагмент програми.
5. Яким чином реалізувати задачу визначення найкоротшого шля­ху між усіма парами вершин заданого графа і відповідних їм шляхів?

7. Домашнє завдання.

Вивчити конспект.

Виконати завдання 1.

Алгоритм Флойда