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

Лабораторна робота № 4

«Визначення найкоротшого шляху в графі»

Мета.  

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

Розвиваюча. Розвивати логічне та алгоритмічне мислення, вміння застосовувати набуті знання.

Виховна. Виховувати наполегливість, самостійність, культуру оформлення

План

• Актуалізація опорних знань.
• ТБ.
• Практична робота.
• Приклади.
• Підсумки  уроку.
• Домашнє завдання.

Хід уроку

1. Організація класу.

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

3. Інструктаж БЖД.

Інструктаж з ТБ при роботі з ПК та в комп’ютерному класі.

4. Лабораторна робота № 4 «Визначення найкоротшого шляху в графі».

Теоретичні відомості

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

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.

Завдання

Знайдемо для мережі, показаної на малюнку, найкоротші шляхи між будь-якими двома вузлами. Відстань між вузлами цієї мережі проставлені на малюнку біля відповідних ребер.

Приклади завдань

4. Підсумки уроку.

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

Повторити “Визначення найкоротшого шляху в графі”.