Алгоритм розрахунку матриці найкоротших відстаней на ділянках мережі методом Флойда – Уоршелла

1. Визначити матрицю , кожний елемент якої ( ) є довжина найкоротшої дуги між вершинами i та j заданої транспортної мережі. Якщо такої дуги не існує, покласти значення елемента рівним ∞. Крім того, покласти значення діагонального елемента рівним 0.

2. Для цілого m, послідовно приймаючого значення від 1 до N, визначити за елементами матриці елементи матриці .

3. Алгоритм закінчується отриманням матриці всіх найкоротших шляхів , де N - кількість вершин графа.

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

(1.1)

де – елемент матриці ;

– елементи матриці , знайденої на попередньому кроці алгоритму.

Результати розрахунків кожного етапу представити у табличному вигляді і привести у додатках до курсового проекту. Варіант розширеної матриці надати у пояснювальній записці (табл. 1.1).

Таблиця 1.1

Розширена матриця найкоротших відстаней

Номер району відправлення	Номер району прибуття
		…	n
	0	l₁₂	…	l₁_n
1→2	…	1→…→n
	l₂₁	0	…	l₂_n
2→1	…	2→…→n
…	…	…	0	…

n	l_n1	l_n₂	…	0
n→…→1	n→…→2	…

де n – кількість транспортних районів

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Методичні рекомендації	\|	Навчально-методичне видання

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.