Оптимальний шлях 0-10-9-8

Аналіз результатів розв’язання задачі.

Представлення результатів роботи програми.

Розв’язання задачі на контрольному прикладі

По результатам роботи програми оптимальний шлях від заводу збірного залізобетону, що знаходяться в пункті 0 до будівельних майданчиків 1-8 при заданій схемі автомобільних шляхів – це шлях 0-10-9-8.

Інтерфейс програми:

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

Рис.2 Приклад роботи програми

Розрахувавши задачу методом Флойда, ми знайшли відстані від заводу збірного бетону до будівельних майданчиків.

В результаті ми отримуємо дві матриці – матрицю мінімальних відстаней між заводом залізобетону та будівельними майданчиками та матрицю шляхів:

Рис 3. Матриця відстаней Рис 4. Матриця шляхів

· Найкоротша відстань від пункту 0 (завод ЗБК) до пункту 1 (буд. майданчик)становить 7; маршрут 0-1.

· Найкоротша відстань від пункту 0 (завод ЗБК) до пункту 2 (буд. майданчик)становить 7; маршрут 0-1-2.

· Найкоротша відстань від пункту 0 (завод ЗБК) до пункту 3 (буд. майданчик)становить 12, проте якщо ми будемо рухатись від пункту 3 до пункту 1, відстань між ними буде становити 7. маршрут 0-1-3.

· Найкоротша відстань від пункту 0 (завод ЗБК) до пункту 4 (буд. майданчик) становить 11; маршрут 0-1-3-4.

· Найкоротша відстань від пункту 0 (завод ЗБК) до пункту 5 (буд. майданчик) становить 12; маршрут 0-1-5.

· Найкоротша відстань від пункту 0 (завод ЗБК) до пункту 6 (буд. майданчик) становить 19; маршрут 0-1-3-6.

· Найкоротша відстань від пункту 0 (завод ЗБК) до пункту 7 (буд. майданчик) становить 21; маршрут 0-1-5-7.

· Найкоротша відстань від пункту 0 (завод ЗБК) до пункту 8 (буд. майданчик) становить 17; маршрут 0-10-9-8.

До п.8- найкоротша відстань — 17.

Найдовший шлях до п.8 — 21

Дата добавления: 2015-08-31