• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

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

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

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

(1.1)

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

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

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

Таблиця 1.1

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

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

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

1. IV. Алгоритм вирішення задачі
2. IV. Алгоритм розв’язання задачі
3. IV. Алгоритм розв’язання задачі
4. IV. Алгоритм розв’язання задачі
5. IV. На четвертому етапі, виходячи із позиції кожної СОБ на матриці АДЛ, вибирають для неї відповідну стратегію.
6. Rete-алгоритм
7. VII. Нахождение общего решения методом характеристик
8. Абонентський стик ISDN мережі
9. Автоматичне налагодження їх індуктивності на ємність мережі для забезпе1
10. АЛГОРИТМ
11. АЛГОРИТМ
12. АЛГОРИТМ

Переглядів: 1277