Контрольні запитання:

1. До яких методів програмування належить угорський метод?

2. Які ще задачі можна вирішувати вказаним методом?

3. Що таке двочастковий граф? Повний двочастковий граф? Навести приклади.

4. Що значать «червоні нулі» у методі?

Література [7]

Практична робота 16. Універсальний метод знаходження найкоротшого шляху.

Мета: набути практичні навички знаходження найкоротших відстаней методом Флойда

Задача

Дана транспортна мережа (рис.16.1).

Рис. 16.1 Транспортна мережа

Завдання

1. Відстані на малюнку розрахувати згідно свого варіанту.

2. Визначити найкоротші відстані між 1 та 11 вершинами транспортної мережі.

Методичні вказівки

Алгоритм Флойда. Цей алгоритм знаходить найкоротші шляхи між будь-якими двома вузлами мережі. У цьому алгоритмі мережа представлена у виді квадратної матриці з n рядками і n стовпцями. Елемент (i,j) дорівнює відстані d_ij від вузла і до вузла j, яке має кінцеве значення, якщо існує дуга (i,j), і дорівнює нескінченності в противному випадку.

Нехай є три вузли i, j та k і задані відстані між ними (рис. 16.2). Якщо виконується нерівність d_ij+ d_jk< d_ik, те доцільно замінити шлях i  k шляхом i  j  k. Така заміна (далі її будемо умовно називати трикутним оператором) виконується систематично в процесі виконання алгоритму Флойда.

Рис. 16.2 Трикутний оператор.

Алгоритм Флойда вимагає виконання наступних дій.

Крок 0. Визначаємо початкову матрицю відстаней D0 матрицю послідовності вузлів S₀. Діагональні елементи обох матриць позначаються знаком “”, що вказує: ці елементи в обчисленнях не фігурують. Припускаємо k=1.

Основний крок k. Задаємо рядок k як ведучий рядок і ведучий стовпець. Розглядаємо можливість застосування трикутного оператора до всіх елементів d_ij матриці D_k-1. Якщо виконується нерівність

d_ik+ d_kj<d_ij, (ik, jk и ij),

тоді виконуються наступні дії:

а) створюємо матрицю D_k шляхом заміни в матриці D_k-1 елемента d_ij на суму d_ij- d_kj.

b) створюємо матрицю S_k шляхом заміни в матриці S_k-1 елемента s_ij на k. Припускаючи k=k+1 повторюємо шаг k.

	1	2	…	j	…	n
1		d12	…	d1j	…	d1n
2	d21		…	d2j	…	d2n
. . .	. . .	. . .	. . .	. . .	. . .	. . .
i D0=	di1	di2	…	dij	…	din
. . .	. . .	. . .	. . .	. . .	. . .	. . .
n	dn1	dn2	…	dnj	…	

	1	2	…	j	…	n
1		2	…	j	…	n
2	1		…	j	…	n
. . .	. . .	. . .	. . .	. . .	. . .	. . .
i S0=	1	2	…	j	…	n
. . .	. . .	. . .	. . .	. . .	. . .	. . .
n	1	2	…	j	…	

Пояснимо дії, виконувані на k-м кроці алгоритму, представивши матрицю D_k-1 так, як вона показана на рис.16.3. На цьому малюнку рядок k є ведучим. Рядок i – будь-який рядок з номером від 1 до k-1, а строка p – довільний рядок з номером від k+1 до n. Аналогічно стовпець j представляє будь-який стовпець з номером від 1 до k-1, а стовпець q – довільний з номером від k+1 до n. Аналогічно стовпець j представляє будь-який стовпець з номером від k+1 до n. Трикутний оператор виконується в таким чином. Якщо сума елементів ведучих рядка і стовпця (показаних у квадратиках) менше елементів, що знаходяться на перетинанні стовпця і рядка (показаних у квадратиках) і відповідають розглянутим ведучим елементами, замінюються ці елементи визначеною сумою.

Після реалізації n кроків алгоритму визначення по матрицям D_n и S_n найкоротшого шляху між вузлами i та j виконується за наступними правилами.

Відстань між вузлами i та j дорівнює елементу d_ij в матриці D_n.

Проміжні вузли шляху від вузла i до вузла j визначається по матриці S_n. Пусть s_ij=k, тоді маємо шлях i  k  j. Якщо далі s_ik=k та s_kj=j, тоді вважаємо, що весь шлях визначений, тому що знайдені всі проміжні вузли. У противному випадку повторюємо описану процедуру для шляхів від вузла і до вузла k і від вузла k до вузла j.

Рис. 16.3 Геометрична інтерпретація ведучих: стовпця та рядка.