вікно програми
У полі програми з'явиться порожня робоча область з ім'ям «Без імені». На неї слід поміщати вершини, дуги ребра графа, їх також можна видаляти, зім'яти їм вага, вибравши відповідні інструменти на панелі інструментів. Щоб знайти найкоротший шлях слід вибрати інструмент «пошук найкоротшого шляху», поставити указтель миші на вихідну вершину і перетягнути його до кінцевої. Приклад знаходження шляху показаний на малюнку 9.
Рисунок 9 - Пошук найкоротшого шляху
Зауважимо, що стрілка з'єднує, потрібні нам вершини забарвлюється в потрібний колір. Після цього ми відпускаємо ліву кнопку миші і бачимо такі діалогове вікно:
Рисунок 10 - Завершений пошук шляху.
Виходячи з малюнка 10, ми можемо бачити, що дуги, складові найкоротший шлях між нашими вершинами забарвилися в синій колір, а також з'явилося вікно коментаря, в якому вказується довжина знайденого шляху.
3.4 Контрольний приклад
Припустимо, є деякий граф G (малюнок 11).
Малюнок 11
Знайдемо для всіх пар його вершин найкоротші шляхи, використовуючи алгоритм Флойда.
Побудуємо матриці D і P для початкового стану графа.
Рисунок 12 - Початковий стан
Крок 2.
Рис. 13. Матриці D і P
Крок 3.
Рис. 14. Матриці D і P
Крок 3
Малюнок 15 - Матриці D і P
Крок 4
Малюнок 16 - Матриці D і P
Кінцеві матриці D4 і P4 містять всю інформацію, необхідну для визначення найкоротших шляхів між будь-якими двома вершинами. Наприклад, найкоротша відстань між вершинами 1 і 5 одно d=12.
Для знаходження відповідних маршрутів нагадаємо, що сегмент маршруту (i, j) складається з ребра (i, j) тільки в тому випадку, коли P=j. В іншому випадку вузли i та j пов'язані, принаймні, через один проміжний вузол. Наприклад, оскільки S=??4 і S=5, спочатку найкоротший маршрут між вузлами 1 і 5 буде мати вигляд 1 -> 4 -> 5. Але так як S не одно 4, вузли 1 і 4 в певному шляху не пов'язані одним ребром (але в вихідної мережі вони можуть бути пов'язані безпосередньо). Далі слід визначити проміжний вузол (вузли) між першим і четвертим вузлами. Маємо S=2 і S=4, тому маршрут 1 -> 4 замінюємо 1 -> 2 -> 4. Оскільки S=??2 і S=4, інших проміжних вузлів немає. Комбінуючи певні сегменти маршруту, остаточно отримуємо наступний найкоротший шлях від вузла 1 до вузла 5: 1 -> 2 -> 4 -> 5. Довжина цього шляху дорівнює 12.
Тепер знайдемо найкоротші шляхи, використовуючи програму, розроблену при виконанні даної курсової роботи.
Висновок
В ході виконання даної курсової роботи ми навчилися вибирати вхідні дані, аналізувати поставлене завдання, вибирати методи і способи її вирішення, аналізувати їх, аналізувати предметну область, обрану для вирішення конкретної поставленої задачі, складати алгоритм виконання програми та структурні схеми до кожного з методів, розробляти програмну документацію і по ній розробляти саму програму.
В результаті виконання курсової роботи ми отримали програмний продукт для знаходження найкоротших шляхів між усіма вершинами орієнтованого та нео...
