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

Задача про найкоротший шлях

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

Приклад 2.2. На рис. 2.7 задана мережа, в якій вузол 1 – це початкова точка (вихідний пункт), а вузол 7 – кінцева точка (пункт призначення).

Рис. 2.7.

Потрібно знайти найкоротший шлях з пункту 1 в пункт 7 і його довжину.

Розв’язок. Позначимо через — відстань на мережі між суміжними вузлами і та j, — найкоротшу відстань між першим та j-им вузлом. Процедура знаходження найкоротшого шляху завершиться тоді, коли буде знайдено . Для знаходження використовуємо формулу .

Проведемо поетапне знаходження :

1. .
2. 
3. 
4. 
5. 
6. 

Мінімальна відстань між вузлами 1 і 7 дорівнює 13, а відповідний маршрут 1→2→5→7.

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

1. Взаємне положення площин. Перша позиційна задача
2. Взаємне положення прямої і площини. Друга позиційна задача.
3. Вибухова сила – це здатність людини проявити свої максимальні силові можливості за найкоротший час.
4. Вторая задача анализа на чувствительность
5. З праці В. Леніна «О задачах пролетариата в данной революции»
6. Задача 1
7. Задача 1
8. Задача 1
9. Задача 1.
10. Задача 1.
11. Задача 1.
12. Задача 1.

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