Розробка програмного комплексу по знаходженню найкоротших маршрутів. Курсова робота з Програмування. Робота № 519795

Перехід до торгівельного партнера Binance

Розробка програмного комплексу по знаходженню найкоротших маршрутів

Інформація про навчальний заклад

ВУЗ:

Інші

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра інформаційних систем і технологій

Інформація про роботу

Рік:

2011

Тип роботи:

Курсова робота

Предмет:

Програмування

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки, молоді та спорту України Національний транспортний університет Кафедра інформаційних систем і технологій КУРСОВА РОБОТА на тему "Розробка програмного комплексу по знаходженню найкоротших маршрутів" з дисципліни "Новітні платформи програмування" Національний транспортний університет (назва вищого навчального закладу) Кафедра інформаційних систем та технологій Дисципліна Новітні платформи програмування Напрям "Комп'ютерні науки", спеціальність "Інформаційні управляючі системи та технології"Курс 3 Група Семестр 5 ЗАВДАННЯ на курсову (розрахунково-графічну) роботу студента (прізвище, ім'я, по батькові) 1. Тема проекту (роботи)_"Розробка програмного комплексу по знаходженню найкоротших маршрутів"___________________________________________________________________ Строк здачі студентом закінченого проекту (роботи)- Вихідні дані до проекту (роботи) постановка задачі 4. Зміст розрахунково-пояснювальної записки (перелік питань, які підлягають розробці)1. Постановка задачі та аналіз предметної області. 2. Ручний підрахунок. 3. Опис роботи створеного продукту. 5. Перелік графічного матеріалу (з точним зазначенням обов'язкових креслень) Орграф згідно варіанту. Головне вікно програми. Вікно вводу початкової вершини. Вікно вводу точності розрахунків. 6. Дата видачі завдання КАЛЕНДАРНИЙ ПЛАН № п/п Назва етапів розрахунково-графічної роботи Строк виконання етапів роботи Підписи студента, керівника 1. Отримання теми розрахунково-графічної роботи 2. Узгодження постановки задачі з керівником 3. Пошук та вивчення літератури з питань курсової роботи 4. Аналіз предметної області 6. Узгодження предметної області з керівником 5. Розробка алгоритмів рішення задачі 6. Узгодження алгоритмів з керівником 7. Узгодження з керівником інтерфейсу користувача 8. Розробка інформаційного забезпечення 9. Розробка програмного забезпечення 10. Налагодження розрахункової частини програми 11. Розробка та налагодження інтерфейсної частини програми 12. Узгодження з керівником набору тестів для контрольного прикладу 13. Тестування програми 14. Підготовка пояснювальної записки 15. Здача курсової (розрахунково-графічної) роботи на перевірку 16. Захист Студент (підпис) Керівник (підпис) (прізвище, ім'я, по батькові) АНОТАЦІЯ Курсова робота містить: 35 сторінок машинописного тексту, 7 рисунків, 6 літературних джерел, 1 додаток. У курсовій роботі розроблена програма реалізації пошуку найкоротшій відстані між вершинами орієнтованого графа. Програмний комплекс припускає реалізацію задачі трьома методами. Перший метод Дейкстри, знаходить найкоротші маршрути від заданої вершини до всіх інших, другий метод Флойда і третій матричний метод визначають найкоротші маршрути між будь-якою парою вершин. Дана програма написана з допомогою мови програмування C# в середовищі Microsoft Visual Studio 2008.. При написанні програми основна увага була приділена зручності роботи користувача з програмою і побудові дружнього інтерфейсу. Результати тестування показали, що програма працює вірно у всіх передбачуваних ситуаціях. ЗМІСТ Вступ 6 Розділ 1. Аналіз предметної області. Постановка задачі 7 1.1 Поняття про граф, алгоритми знаходження найкоротших шляхів 7 1.1.1 Алгоритм Дейкстри 8 1.1.2 Алгоритм Флойда 10 1.1.3 Матричний метод 12 1.2 Мова та середовище програмування 13 1.2.1 Переваги мови C# 14 Розділ 2. Рішення задачі 17 Розділ 3. Опис створеної програми 31 Висновок 34 Список використаних джерел 35 Додаток A 36 Вступ Завдяки своєму широкому застосуванню, теорія про знаходження найкоротших шляхів останнім часом інтенсивно розвивається. Знаходження найкоротшого шляху - життєво необхідно і використовується практично скрізь, починаючи від перебування оптимального маршруту між двома об'єктами на місцевості (наприклад, найкоротший шлях від будинку до університету), в системах автопілота, для знаходження оптимального маршруту при перевезеннях, комутації інформаційного пакету в Internet і т. д. Найкоротший шлях розглядається за допомогою певного математичного об'єкту, званого графом. Існують три найбільш ефективних алгоритму знаходження найкоротшого шляху: - алгоритм Дейкстри (використовується для знаходження оптимального маршруту між двома вершинами); - алгоритм Флойда (для знаходження оптимального маршруту між усіма парами вершин); - матричний метод (для знаходження оптимального маршруту між усіма парами вершин). Зазначені алгоритми легко виконуються при малій кількості вершин у графі. При збільшенні їх кількості завдання пошуку найкоротшого шляху ускладнюється. Тут на допомогу приходить сучасна техніка. Комп'ютерні засоби та інформаційні технології підвищили можливості такого всеосяжного методу вивчення і створення, як моделювання об'єктів, явищ і процесів - як тих, що існують у природі, так і тих, що створюються людиною штучно. Кількість об'єктів ускладнювалися, збільшувалися, і натурне моделювання (макети споруд) стало невигідним, не економним. Тому для вивчення почали застосовувати математику. Використання математичних моделей - рівняння, нерівності, формули і тому подібне називається математичним моделюванням, для розвитку і пристосування якого потрібні були ефективні чисельні методи. Реалізувати великий потенціал математичного моделювання неможливо без потужних засобів автоматизації обчислень, якими є комп'ютери. Розділ 1. Аналіз предметної області. Постановка задачі Виконання курсової роботи має на меті закріплення практичних навичок у вирішенні практичних завдань з розробки програмних продуктів на основі сучасних платформ програмування. Курсова робота припускає розробку програмного комплексу, що трьома методами вирішує задачу визначення найкоротших маршрутів у середовищі орієнтованих графів. Перший метод Дейкстри знаходить найкоротші маршрути від заданої вершини до всіх інших, другий метод Флойда і третій матричний метод визначають найкоротші маршрути між будь-якою парою. Проектування програмного додатку ведеться у відповідності з наступними технологічними принципами: покрокової кристалізації; застосуванням псевдомови; використанням різних абстрактних типів даних. 1.1 Поняття про граф, алгоритми знаходження найкоротших шляхів Граф - це множина точок (вершин), які з’єднані між собою лініями, що називаються дугами або ребрами. Граф задається множиною точок (вершин) х1, х2,..., хn. (яке позначається через Х) і безліччю ліній (ребер) а1, а2,...,аm. (яке позначається символом А), що з'єднують між собою всі або частину цих точок. Таким чином, граф повністю задається (і позначається) парою (Х, А). Якщо ребра з множини А орієнтовані, що зазвичай показується стрілкою, то вони називаються дугами, і граф з такими ребрами називається орієнтованим графом (рис. 1.1). Рис.1.1. Орієнтований граф. Рис.1.2. Неорієнтований граф. Наприклад, якщо дорога має не двохсторонній, а односторонній рух то напрямок цього руху буде показано стрілкою. Якщо ребра не мають орієнтації, то граф називається неорієнтованим, (двосторонній рух) (рис. 1.2). У орієнтованому графі дуга позначається впорядкованої парою, що складається з початкової та кінцевої вершин, її напрямок передбачається заданим від першої вершини до другої. Шляхом (або орієнтованим маршрутом) орієнтованого графа називається послідовність дуг, в якій кінцева вершина будь-якої дуги, відмінною від останньої, є початковою вершиною наступної. 1.1.1 Алгоритм Дейкстри Описуваний алгоритм дозволяє знаходити в графі найкоротший шлях між двома виділеними вершинами s і t при позитивних довжинах дуг. Цей алгоритм, запропонований в 1959 р. Дейкстрой, вважається одним з найбільш ефективних алгоритмів рішення задачі. Головна ідея, що лежить в основі алгоритму Дейкстри, доволі проста. Припустимо, що нам відомі m вершин, найближчих до вершини s (близькість будь-якої вершини x до вершини s визначається довжиною найкоротшого шляху, що веде з s в x). Нехай також відомі самі найкоротші шляхи, що сполучають вершину s з виділеними m вершинами. Покажемо тепер, як може бути визначена (m+1)-ша найближча до s вершина. Зафарбуємо вершину s і m найближчих до неї вершин. Побудуємо для кожної незабарвленої вершини y шляхи, що безпосередньо сполучають за допомогою дуг (х, у) кожну забарвлену вершину х з у. Виберемо з цих шляхів найкоротший, і рахуватимемо його умовно найкоротшим шляхом з вершини s у вершину y. Яка ж з незабарвлених вершин є (m+1)-ою найближчою до s вершиною? Та, для якої умовно найкоротший шлях має найменшу довжину. Це обумовлюється тим, що найкоротший шлях з вершини s в (m+1)-у найближчу вершину при позитивному значенні довжин усіх дуг повинен містити як проміжні лише забарвлені вершини, тобто вершини, що входять до числа m вершин, найближчих до вершини s. Отже, якщо відомі m найближчих до s вершин, то (m+1)-ша найближча до s вершина може бути знайдена так, як це описано вище. Починаючи з m=0, описана процедура може повторюватися до тих пір, поки не буде отриманий найкоротший шлях, що веде з вершини s до вершини t. Маючи на увазі приведені міркування, ми можемо тепер формально описати алгоритм Дейкстри. Алгоритм Кожній вершині X в ході алгоритму привласнюється число d(x), рівне довжині найкоротшого шляху з вершини S у вершину X і що включає тільки забарвлені вершини. Покласти d(s)=0 і d(x)=∞ для усіх інших вершин графа. Забарвлюємо вершину S і вважаємо y=S, де y - остання забарвлена вершина. Для кожної незабарвленої вершини X перераховується величина d(x) по наступній формулі: Якщо d(x)=∞ для усіх незабарвлених вершин, то алгоритм закінчується оскільки відсутні шляхи з вершини S в незабарвлені вершини. Інакше забарвлюється та вершина, для якої величина d(x) є мінімальною. Забарвлюється і дуга, що веде в цю вершину відповідно до виразу (1.1) і вважаємо y=x. Якщо y=t, найкоротший шлях з s в t знайдений. Інакше переходимо до кроку 2. Кожного разу забарвлюється вершина і дуга, що заходить в цю вершину. Забарвлені дуги не можуть утворювати цикл, а утворюють в початковому графові дерево з коренем (початком) у вершині s. Це дерево називають орієнтованим деревом найкоротших шляхів. Шлях з s в t належить цьому дереву. При пошуку одного найкоротшого шляху процедура нарощування завершується досягши кінцевої вершини цього шляху. Для цього процедуру нарощування орієнтованого дерева триває до тих пір, поки усі вершини не будуть включені. Таким чином, ми отримуємо орієнтоване дерево найкоротших шляхів, яке є покриваючим деревом графа. Іноді в графі є декілька найкоротших шляхів. Найкоротший шлях буде єдиним, якщо в алгоритмі жодного разу не виникає неоднозначність при фарбуванні дуги. Відмітимо, що головною умовою успішного застосування алгоритму Дейкстри до завдання на графі являється позитивність довжин дуг цього графа. 1.1.2 Алгоритм Флойда Алгоритм Флойда є одним з методів пошуку найкоротших шляхів у графі. На відміну від алгоритму Дейкстри, який дозволяє при доведенні до кінця побудувати орієнтоване дерево найкоротших шляхів від деякої вершини, метод Флойда дозволяє знайти довжини усіх найкоротших шляхів в графі. Звичайно це завдання може бути вирішене і багатократним застосуванням алгоритму Дейкстри (кожного разу послідовно вибираємо вершину від першої до N-ої, поки не отримаємо найкоротші шляхи від усіх вершин графа), проте реалізація подібної процедури зажадала б значних обчислювальних витрат. Перш ніж представляти алгоритми, необхідно ввести деякі позначення. Пронумеруємо вершини початкового графа цілими числами від 1 до N. Позначимо через di,jm довжину найкоротшого шляху з вершини i у вершину j, який як проміжні може містити тільки перші m вершин графа. (Нагадаємо, що проміжною вершиною шляху є будь-яка вершина, що належить йому, не співпадаюча з його початковою або кінцевою вершинами.) Якщо між вершинами i і j не існує жодного шляху вказаного типу, то умовно вважатимемо, що di,jm=∞. З цього визначення величин di,jm слідує, що величина di,j0, представляє довжину найкоротшого шляху з вершини i у вершину j, що не має проміжних вершин, тобто довжину найкоротшої дуги, сполучаючою i з j (якщо такі дуги присутні в графі). Для будь-якої вершини i покладемо di,im=0. Відмітимо далі, що величина di,jm представляет довжину найкоротшого шляху між вершинами i і j. Позначимо через Dm матрицю розміру NxN, елемент (i, j) якої співпадає з di,jm. Якщо в початковому графові нам відома довжина кожної дуги, то ми можемо сформувати матрицю D0. Наша мета полягає у визначенні матриці DN, що представляє найкоротші шляхи між усіма вершинами даного графа. У алгоритмі Флойда початковою виступає матриця D0. Спочатку з цієї матриці обчислюється матриця D1. Потім по матриці D1 обчислюється матрицав D2 і т. д. Процес повторюється до тих пір, поки по матриці DN- 1 не буде вичислена матриця DN. Розглянемо основну ідею, що лежить в основі алгоритму Флойда. Суть алгоритму Флойда полягає в перевірці того, чи не виявиться шлях з вершини i у вершину j коротше, якщо він проходитиме через деяку проміжну вершину m. Припустимо, що нам відомі: найкоротший шлях з вершини i у вершину m, в якому як проміжні допускається використання тільки перших (m-1) вершин; найкоротший шлях з вершини m у вершину j, в якому як проміжні допускається використання тільки перших (m-1) вершин; найкоротший шлях з вершини i у вершину j, в якому як проміжні допускається використання тільки перших (m-1) вершин. Оскільки по припущенню початковий граф не може містити контурів негативної довжини, один з двох шляхів – шлях, співпадаючий з представленим в пункті 3, або шлях, що є об'єднанням шляхів з пунктів 1 і 2, - має бути найкоротшим шляхом з вершини i у вершину j, в якому як проміжні допускається використання тільки перших m вершин. Таким чином Із співвідношення видно, що для обчислення елементів матриці Dm необхідно знати лише елементи матриці Dm-1. Більше того, відповідні обчислення можуть бути проведені без звернення до початкового графа. Тепер ми в змозі дати формальний опис алгоритму Флойда для знаходження на графі найкоротших шляхів між усіма парами вершин. Алгоритм Пронумерувати вершини графа від 1 до N цілими числами, визначити матрицю D0, кожен елемент di,j якою є довжина найкоротшої дуги між вершинами i і j. Якщо такої дуги немає, покласти значення елементу рівним ∞. Крім того, покласти значення діагонального елементу di,i рівним 0. Для цілого m, послідовно приймаючого значення 1..N визначити по елементах матриці Dm-1 елементи Dm. Алгоритм закінчується отриманням матриці усіх найкоротших шляхів DN, N - число вершин графа. Нагадаємо, для визначення по відомих елементах матриці Dm-1 елементів матриці Dm в алгоритмі Флойда застосовується рекурсивне співвідношення (1.2). 1.1.3 Матричний метод Нехай є орієнтований граф G = (V, Е), у якого всі дуги мають позитивні мітки (вартості дуг). Задача полягає в знаходженні вартості найкоротших шляхів від будь-якої вершини графа до всіх інших вершин графа G. Можна представити граф G у вигляді карти маршрутів рейсових польотів з одного міста в інше, де кожна вершина відповідає місту, а дуга v ⇒ w — рейсовому маршруту з міста v у місто w. Мітка дуги v ⇒ w — це час польоту з міста v у місто w. При цьому може виникнути припущення, що в цьому випадку як модель більше підходить неорієнтованого графа, оскільки мітки дуг v ⇒ w і w ⇒ v можуть збігатися. Але фактично в більшості випадків час польоту в протилежних напрямках між двома містами по-різному. Крім того, допущення про збіг міток дуг v ⇒ w і w ⇒ v не впливає на рішення поставленої задачі. У цьому випадку результатом є мінімальний час перельотів між різними містами. 1.2 Мова та середовище програмування Курсова робота була написана мовою програмування C# в середовищі Microsoft Visual Studio 2008. Visual Studio – це набір інструментів розробки, заснованих на використанні компонентів, і інших технологій для створення потужних, продуктивних застосувань. Крім того, середовище Visual Studio оптимізоване для спільного проектування, розробки і розгортання корпоративних рішень. Visual Studio 2008 Professional Edition є повним набором засобів, що допомагають прискорити процес реалізації задуму розробника. Це рішення було створене щоб забезпечити підтримку проектів створення програмного забезпечення для Інтернету (включаючи ASP.NET AJAX), Windows Vista, Windows Server 2008, випуску 2007 систем Microsoft Office, SQL Server 2008 і пристроїв під управлінням Windows Mobile. Число платформ, на які повинні орієнтуватися розробники відповідно до бізнес-вимог, швидко збільшується. Visual Studio 2008 Professional Edition надає інтегрований набір засобів, що дозволяють врахувати усі ці вимоги шляхом розширення функціональності, доступної в Visual Studio 2008 Standard Edition. Сучасним розробникам доводиться орієнтуватися на широкий спектр платформ, створюючи додатки, що дозволяють організаціям швидко отримувати очікуваний результат. Вбудовані в Visual Studio конструктори і можливості мов програмування дозволяють створювати додатки, здатні зв'язуватися з віддаленими базами даних і таких, що відповідають сподіванням сьогоднішнього бізнесу, а використання переваг середовища .NET Framework 3.5 допомагає скоротити час розробки. 1.2.1 Переваги мови C# Головною особливістю мови C# є її орієнтованість на платформу Microsoft .NET — творці C# ставили за мету надання розробникам природних засобів доступу до всіх можливостей платформи .NET. Творці С# хотіли приховати від розробника якомога більше незначних технічних деталей, включаючи операції по упаковці/розпаковуванню типів, ініціалізації змінних і збірці сміття. Завдяки цьому програміст, що пише на C#, може краще концентруватися на змістовній частині завдання. В процесі рішення цієї задачі проектувальники C# намагалися врахувати уроки реалізації Visual Basic'а, який достатньо успішний в приховуванні деталей реалізації, але недостатньо ефективний для написання масштабних промислових систем: творці C# декларують, що нова мова володіє потужністю С++ і в той же час простотою Visual Basic'а. Ще одна перевага створення нової мови програмування в порівнянні з розширенням тих, що існують полягає в тому, що при створенні нової мови немає необхідності піклуватися про проблеми зворотної сумісності, які зазвичай помітно затрудняють виправлення застарілих проблем і навіть внесення нових властивостей в стандарт мови. Таким чином, C# є новою мовою програмування, орієнтованою на розробку для платформи .NET . 1.3 Постановка задачі Основним завданням даного курсового проекту є програмна реалізація алгоритму пошуку найкоротшого шляху між двома будь-якими вершинами графа. Необхідно передбачити різні результати пошуку, щоб програма не видавала помилок і працювала правильно. Розробка програмного комплексу, що трьома методами вирішує задачу визначення найкоротших маршрутів у середовищі заданого орієнтованого графа (рис. 1.3). Перший метод Дейкстри знаходить найкоротші маршрути від заданої вершини до всіх інших; другий метод Флойда; третій матричний метод визначають найкоротші маршрути між будь-якою парою вершин; Рис.1.3. Заданий орграф Проектування програмного додатку ведеться у відповідності з наступними технологічними принципами: покрокової кристалізації; застосуванням псевдомови; використанням різних абстрактних типів даних. Структура проектованого програмного комплексу повинна включати три основні компоненти: процедуру визначення найкоротших маршрутів по методу Дейкстри; процедуру визначення найкоротших маршрутів по методу Флойда; процедуру визначення найкоротших маршрутів по матричному методу. Розділ 2. Рішення задачі В цьому розділі будуть наведені розрахунки зроблені в ручну за допомогою кожного з методів. 2.1 Ручний розрахунок за алгоритмом Дейкстри Матриця довжин дуг для заданого графа (рис. 1.3) має вигляд: ∞ 10 ∞ 100 30 ∞ 10 ∞ 80 ∞ 50 ∞ ∞ ∞ ∞ 40 ∞ 10 ∞ ∞ ∞ ∞ ∞ 60 ∞ ∞ 70 ∞ ∞ ∞ ∞ ∞ ∞ 60 20 ∞ Стартова вершина, від якої будується дерево найкоротших шляхів, - вершина 1. Задаємо стартові умови: d(1)=0, d(x)=∞. Забарвлюємо вершину 1, y=1. Знаходимо найближчу вершину до забарвленої нами, використовуючи формулу (1.1) : d(2)=min{d(2) ; d(1)+a(1,2)}=min{∞; 0+10}=10 d(3)=min{d(3) ; d(1)+a(1,3)}=min{∞; 0+∞}=∞ d(4)=min{d(4) ; d(1)+a(1,4)}=min{∞; 0+100}=100 d(5)=min{d(5) ; d(1)+a(1,5)}=min{∞; 0+30}=30 d(6)=min{d(6) ; d(1)+a(1,6)}=min{∞; 0+∞}=∞ Мінімальну довжину має шлях від вершини 1 до вершини 2 d(2)=10. включаємо вершину №2 в поточне орієнтоване дерево, а також дугу, яка веде в цю вершину. Відповідно виразу це дуга (1,2). d(3)=min{d(3) ; d(2)+a(2,3)}=min{∞; 10+80}=90 d(4)=min{d(4) ; d(2)+a(2,4)}=min{100; 10+∞}=100 d(5)=min{d(5) ; d(2)+a(2,5)}=min{30; 10+50}=30 d(6)=min{d(6) ; d(2)+a(2,6)}=min{∞; 10+∞}=∞ Мінімальну довжину має шлях від вершини 1 до вершини 5 d(5)=30. Включаємо вершину №5 в поточне орієнтоване дерево, а також дугу, яка веде в цю вершину. Згідно виразу це дуга (1,5). d(3)=min{d(3) ; d(5)+a(5,3)}=min{90; 30+70}=90 d(4)=min{d(4) ; d(5)+a(5,4)}=min{100; 30+∞}=100 d(6)=min{d(6) ; d(5)+a(5,6)}=min{∞; 30+∞}=∞ Мінімальну довжину має шлях від вершини 1 до вершини 3 d(6)=90. Включаємо вершину №3 в поточне орієнтоване дерево, а також дугу, яка веде в цю вершину. Згідно виразу це дуга (2,3). d(4)=min{d(4) ; d(3)+a(3,4)}=min{100; 90+40}=100 d(6)=min{d(6) ; d(3)+a(3,6)}=min{∞; 90+10}=100 Мінімальну довжину має шлях від вершини 1 до вершини 4 d(4)=100. Включаємо вершину №4 в поточне орієнтоване дерево, а також дугу, яка веде в цю вершину. Згідно виразу це дуга (1,4). d(6)=min{d(6) ; d(4)+a(4,6)}=min{100; 100+60}=100 Мінімальну довжину має шлях від вершини 1 до вершини 6 d(6)=100. Включаємо вершину №6 в поточне орієнтоване дерево, а також дугу ведучу в цю вершину. Згідно з вираження це дуга (3,6). Ми отримали орієнтоване дерево найкоротших шляхів що починаються у вершині №1 для початкового графа. d(1)=1 Довжина маршруту L=0 d(2)=1-2 Довжина маршруту L=10 d(3)=1-2-3 Довжина маршруту L=90 d(4)=1-4 Довжина маршруту L=100 d(5)=1-5 Довжина маршруту L=30 d(6)=1-2-3-6 Довжина маршруту L=100 2.2 Ручний розрахунок за алгоритмом Флойда На підставі початкових даних (рис. 1.3) формуємо матрицю довжин найкоротших дуг D0, кожен елемент якої дорівнює довжині найкоротшої дуги між вершинами i і j. Якщо такої дуги немає, покладемо значення елементу рівним ∞. D0= 0 10 ∞ 100 30 ∞ 10 0 80 ∞ 50 ∞ ∞ ∞ 0 40 ∞ 10 ∞ ∞ ∞ 0 ∞ 60 ∞ ∞ 70 ∞ 0 ∞ ∞ ∞ ∞ 60 20 0 На підставі матриці D0, вичислимо послідовно усі елементи матриці D1. Для цього ми використовуємо рекурентне співвідношення di,j1=min{ di,10+ d1,j0; di,j0}. d1,11=min{d1,10+d1,10d1,10}=min{0+0; 0}=0d1,21=min{d1,10+d1,20d1,20}=min{0+10; 10}=10d1,31=min{d1,10+d1,30d1,30}=min{0+∞; ∞}=∞d1,41=min{d1,10+d1,40d1,40}=min{0+100; 100}=100d1,51=min{d1,10+d1,50d1,50}=min{0+30; 30}=30d1,61=min{d1,10+d1,60d1,60}=min{0+∞; ∞}=∞d2,11=min{d2,10+d1,10d2,10}=min{10+0; 10}=10d2,21=min{d2,10+d1,20d2,20}=min{10+10; 0}=0d2,31=min{d2,10+d1,30d2,30}=min{10+∞; 80}=80d2,41=min{d2,10+d1,40d2,40}=min{10+100; ∞}=110d2,51=min{d2,10+d1,50d2,50}=min{10+30; 50}=40d2,61=min{d2,10+d1,60d2,60}=min{10+∞; ∞}=∞d3,11=min{d3,10+d1,10d3,10}=min{∞+0; ∞}=∞d3,21=min{d3,10+d1,20d3,20}=min{∞+10; ∞}=∞d3,31=min{d3,10+d1,30d3,30}=min{∞+∞; 0}=0d3,41=min{d3,10+d1,40d3,40}=min{∞+100; 40}=40d3,51=min{d3,10+d1,50d3,50}=min{∞+30; ∞}=∞d3,61=min{d3,10+d1,60d3,60}=min{∞+∞; 10}=10d4,11=min{d4,10+d1,10d4,10}=min{∞+0; ∞}=∞d4,21=min{d4,10+d1,20d4,20}=min{∞+10; ∞}=∞d4,31=min{d4,10+d1,30d4,30}=min{∞+∞; ∞}=∞d4,41=min{d4,10+d1,40d4,40}=min{∞+100; 0}=0d4,51=min{d4,10+d1,50d4,50}=min{∞+30; ∞}=∞d4,61=min{d4,10+d1,60d4,60}=min{∞+∞; ∞}=∞d5,11=min{d5,10+d1,10d5,10}=min{∞+0; ∞}=∞d5,21=min{d5,10+d1,20d5,20}=min{∞+10; ∞}=∞d5,31=min{d5,10+d1,30d5,30}=min{∞+∞; 70}=70d5,41=min{d5,10+d1,40d5,40}=min{∞+100; ∞}=∞d5,51=min{d5,10+d1,50d5,50}=min{∞+30; 0}=0d5,61=min{d5,10+d1,60d5,60}=min{∞+∞; ∞}=∞d6,11=min{d6,10+d1,10d6,10}=min{∞+0; ∞}=∞d6,21=min{d6,10+d1,20d6,20}=min{∞+10; ∞}=∞d6,31=min{d6,10+d1,30d6,30}=min{∞+∞; ∞}=∞d6,41=min{d6,10+d1,40d6,40}=min{∞+100; 60}=60d6,51=min{d6,10+d1,50d6,50}=min{∞+30; 20}=20d6,61=min{d6,10+d1,60d6,60}=min{∞+∞; 0}=0 Представимо матрицю D1, включивши в неї розраховані елементи. D1= 0 10 ∞ 100 30 ∞ 10 0 80 110 40 ∞ ∞ ∞ 0 40 ∞ 10 ∞ ∞ ∞ 0 ∞ 60 ∞ ∞ 70 ∞ 0 ∞ ∞ ∞ ∞ 60 20 0 Аналогічно матриці D1, обчислимо матрицю D2. d1,12=min{d1,21+d2,11d1,11}=min{10+10; 0}=0d1,22=min{d1,21+d2,21d1,21}=min{10+0; 10}=10d1,32=min{d1,21+d2,31d1,31}=min{10+80; ∞}=90d1,42=min{d1,21+d2,41d1,41}=min{10+110; 100}=100d1,52=min{d1,21+d2,51d1,51}=min{10+40; 30}=30d1,62=min{d1,21+d2,61d1,61}=min{10+∞; ∞}=∞d2,12=min{d2,21+d2,11d2,11}=min{0+10; 10}=10d2,22=min{d2,21+d2,21d2,21}=min{0+0; 0}=0d2,32=min{d2,21+d2,31d2,31}=min{0+80; 80}=80d2,42=min{d2,21+d2,41d2,41}=min{0+110; 110}=110d2,52=min{d2,21+d2,51d2,51}=min{0+40; 40}=40d2,62=min{d2,21+d2,61d2,61}=min{0+∞; ∞}=∞d3,12=min{d3,21+d2,11d3,11}=min{∞+10; ∞}=∞d3,22=min{d3,21+d2,21d3,21}=min{∞+0; ∞}=∞d3,32=min{d3,21+d2,31d3,31}=min{∞+80; 0}=0d3,42=min{d3,21+d2,41d3,41}=min{∞+110; 40}=40d3,52=min{d3,21+d2,51d3,51}=min{∞+40; ∞}=∞d3,62=min{d3,21+d2,61d3,61}=min{∞+∞; 10}=10d4,12=min{d4,21+d2,11d4,11}=min{∞+10; ∞}=∞d4,22=min{d4,21+d2,21d4,21}=min{∞+0; ∞}=∞d4,32=min{d4,21+d2,31d4,31}=min{∞+80; ∞}=∞d4,42=min{d4,21+d2,41d4,41}=min{∞+110; 0}=0d4,52=min{d4,21+d2,51d4,51}=min{∞+40; ∞}=∞d4,62=min{d4,21+d2,61d4,61}=min{∞+∞; ∞}=∞d5,12=min{d5,21+d2,11d5,11}=min{∞+10; ∞}=∞d5,22=min{d5,21+d2,21d5,21}=min{∞+0; ∞}=∞d5,32=min{d5,21+d2,31d5,31}=min{∞+80; 70}=70d5,42=min{d5,21+d2,41d5,41}=min{∞+110; ∞}=∞

Курсова робота Програмування

77pazan77

08.02.2013 00:02-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись