Алгоритм Дейкстри

1. Постановка завдання

Справжня курсова робота моделює логічну задачу, яка складається з наступних частин:

1) Вивчення конкретного розділу дискретної математики.

2) Рішення 5-ти задач з вивченої теми з методичним описом.

3) Розробка та реалізація у вигляді програми алгоритму з вивченої теми. Розробка програмного інтерфейсу.

2. Введення

2.1 Теоретична частина

дискретний математика програма інтерфейс

Нехай дано граф G = (X, Г), дугам якого приписані ваги (вартості), що задаються матрицею C = [c ij ]. Задача про найкоротший шляху полягає в знаходженні найкоротшого шляху від заданої початкової вершини sX до заданої кінцевої вершини tX, за умови, що такий шлях існує, тобто за умови tR (s). Тут R (s) - безліч, досяжне з вершини s. Елементи c ij матриці ваг C можуть бути позитивними, негативними або нулями. Єдине обмеження полягає в тому, щоб в G не було циклів з негативним сумарною вагою. Якщо такий цикл Ф все ж існує і x i - деяка його вершина, то, рухаючись від s до x i , обходячи потім Ф досить багато раз і потрапляючи нарешті в t, ми отримаємо шлях з як завгодно малим () вагою. Таким чином, в цьому випадку найкоротшого шляху не існує.

Якщо, з іншого боку, такі цикли існують, але виключаються з розгляду, то знаходження найкоротшого шляху (простий ланцюга) між s і t еквівалентно знаходженню в цьому графі найкоротшого Гамільтона шляху з кінцевими вершинами s і t. Це можна угледіти з наступного факту. Якщо з кожного елемента c ij матриці ваг C відняти досить велике число L, то вийде нова матриця ваг C '= [c ij '], всі елементи c ij 'якої негативні. Тоді найкоротший шлях від s до t - з виключенням негативних циклів - необхідно буде Гамільтона, тобто проходить через всі інші вершини. Так як вага будь-якого гамильтонова шляху з матрицею ваг C 'дорівнює вазі цього шляху з матрицею ваг C, але зменшеному на постійну величину (n-1) Г— L, то найкоротший шлях (Проста ланцюг) від s до t з матрицею C 'буде найкоротшим Гамільтона шляхом від s до t при первісній матриці C. Задача про знаходження найкоротшого Гамільтона шляху набагато складніше, ніж задача про найкоротшому шляху. Тому ми будемо припускати, що всі цикли в G мають невід'ємні сумарна вага. Звідси також випливає, що неорієнтовані дуги (ребра) графа G не можуть мати негативні ваги.

Наступні завдання є безпосередніми узагальненнями сформульованої вище задачі про найкоротшому шляху.

1) Для заданої початкової вершини s знайти найкоротші шляхи між t і всіма іншими вершинами x i X.

2) Знайти найкоротші шляхи між усіма парами вершин.

Окремі випадки, коли всі c ij ненегативні, зустрічаються на практиці досить часто (наприклад, коли c ij є відстанями), так що розгляд цих спеціальних алгоритмів виправдано. Ми будемо припускати, що матриця не задовольняє, взагалі кажучи, умові трикутника, тобто не обов'язково для всіх. В іншому випадку найкоротший шлях між x j і x j складається з однієї єдиної (x j x j ) дуги, якщо така дуга існує, і задача стає тривіальною. Якщо в графі G дуга (x j x j ) відсутня, то її вага покладається рівним.

На практиці часто потрібно знайти не тільки найкоротший шлях, але також другий, третій і т.д. найкоротші шляхи в графі. Маючи цими результатами, можна вирішити, який шлях вибрати в якості найкращого. Крім того, другий, третій і т.д. найкоротші шляху можна використовувати при аналізі В«чутливостіВ» завдання про найкоротший шляху.

Існують також задачі знаходження в графах шляхів з максимальною надійністю і з максимальною пропускною здатністю. Ці завдання пов'язані із завданням про найкоротший шляху, хоча в них характеристика шляху (скажімо, вага) є не сумою, а деякої іншої функцією характеристик (ваг) дуг, що утворюють шлях. Такі завдання можна переформулювати як завдання про найкоротший шлях. Однак можна вчинити інакше: безпосередньо пристосувати для їх вирішення ті методи, які застосовуються в задачах про найкоротший шлях.

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

Найбільш ефективний алгоритм розв'язання задачі про найкоротший (s - t) - шляху спочатку дав Дейкстра. У загальному випадку цей метод заснований на приписуванні вершин часових позначок, причому позначка вершини дає верхню межу довжини шляху від s до цієї вершини. Ці позначки (їх величини) поступово зменшуються за допомогою деякої ітераційної процедури, і на кожному кроці ітерації точно одна з тимчасових позначок стає постійною. Останнє вказує на те, що позначка вже не є верхньою кордоном, а дає точну довжину найкоротшого шляху від s до розглянутої вершині. Опишемо цей метод докладно.

Алгоритм Дейкстри ()

Нехай l (x i ) - позначка вершини x i .

Присвоєння початкових значень

Крок 1 . Покласти і вважати цю позначку постійною. Покласти для всіх x i s і вважати ці позначки тимчасовими. Покласти p = s.

Оновлення позначок

Крок 2 . Для всіх, позначки яких тимчасові, змінити позначки у відповідності з наступним виразом:.

Перетворення помітки в постійну

Крок 3 . Серед всіх вершин з тимчасовими позначками знайти таку, для якої.

Крок 4 . Вважати позначку вершини x i * постійної і покласти p = x i *.

Крок 5 . (1) ( Якщо треба знайти лише шлях від s до t . )

Якщо p = t, то l (p) є довжиною найкоротшого шляху. Останов.

Якщо pt, перейти до кроку 2.

(2) ( Якщо потрібно знайти шляху від s до всіх інших вершин .)

Якщо всі вершини відзначені як постійні, то ці позначки дають довжини найкоротших шляхів. Останов.

Якщо деякі помітки є тимчасовими, перейти до кроку 2.

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

Припустимо, що на деякому етапі постійні позначки дають довжини найкоротших шляхів. Нехай S 1 - безліч вершин з цими позначками, а S 2 - безліч вершин з тимчасовими позначками. В кінці кроку 2 кожною ітерації тимчасова позначка l (x i ) дає найкоротший шлях від s до x i , що проходить повністю по вершин безлічі S 1 . (Так як при кожній ітерації в безліч S 1 включається тільки одна вершина, то оновлення позначки l (x i ) вимагає тільки одного порівняння на кроці 2.)

Нехай найкоротший шлях від s до x i * не проходить повністю по S 1 і містить по крайнього міру одну вершину з S 2 , і нехай x j S 2 - перша така вершина в цьому шляху. Так як за припущенням c ij ненегативні, то частина шляху від x j до x i * повинна мати невід'ємні вага і. Це, однак, суперечить твердженням, що l (x i *) - найменша тимчасова позначка, і, отже, найкоротший шлях до x i * проходить повністю по вершинах безлічі S 1 , і тому l (x i *) є його довжиною.

Так як спочатку безліч S 1 одно (s) при кожній ітерації до S 1... додається x i *, то припущення, що l (x i *) дорівнює довжині найкоротшого шляху x i S 1 , виконується при кожній ітерації. Звідси по індукції випливає, що алгоритм дає оптимальну відповідь.

Якщо потрібно знайти найкоротші шляхи між s та всіма іншими вершинами повного зв'язного графа з n вершинами, то в процесі роботи алгоритму виконуються операцій складання та порівняння на кроці 2 і ще операцій порівняння на кроці 3. Крім того, при здійсненні кроків 2 і 3 необхідно визначити, які вершини тимчасові, а для цього потрібно ще операцій порівняння. Ці величини є верхніми границями для числа операцій, необхідних при відшуканні найкоротшого шляху між заданими вершинами s і t. Вони дійсно досягаються, якщо виявиться, що вершина t буде останньою вершиною, що отримала постійну позначку.

Як тільки довжини найкоротших шляхів від s будуть знайдені (вони будуть заключними значеннями позначок вершин), самі шляху можна отримати за допомогою рекурсивної процедури з використанням співвідношення (*). Так як вершина x i 'безпосередньо передує вершині x i в найкоротшому шляху від s до x i , то для будь-якої вершини x i відповідну вершину x i 'можна знайти як одну з залишилися вершин, для якої

''. (*)

Якщо найкоротший шлях від s до будь-якої вершини x i є єдиним, то дуги (x i ', x i ) цього найкоротшого шляху утворюють орієнтоване дерево з коренем s. Якщо існує кілька В«найкоротшихВ» шляхів від s до якої-небудь іншої вершині, то при деякій фіксованій вершині x i 'співвідношення (*) буде виконуватися для більш ніж однієї вершини x i . У цьому випадку вибір може бути або довільним (якщо потрібен якийсь один найкоротший шлях між s і x i ), або таким, що розглядаються всі дуги (x i ', x i ), що входять до будь-якої з найкоротших шляхів і при цьому сукупність всіх таких дуг утворює не орієнтоване дерево, а загальний граф, званий базою щодо s або коротко - s- базою .

2.2 Завдання з методичним описом

Знайти найкоротші шляхи від вершини 1 до всіх інших вершин графа

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

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 9

x 1

10 3 6 12

x 2

10 18 2 13

x 3

18 25 20 7

x 4

25 5 16 4

x 5

5 10

x 6

20 10 14 15 9

x 7

2 4 14 24

x 8

6 23 15 5

x 9

12 13 9 24 5

Алгоритм працює так:

Крок 1 . .

Перша ітерація

Крок 2 . - Всі позначки тимчасові.

;;;

Крок 3 . відповідає x 7 .

Крок 4 . x 7 отримує постійну позначку l (x 7 ) = 3 + , p = x 7 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Друга ітерація

Крок 2 . - Всі позначки тимчасові.

;;;

Крок 3 . відповідає x 2 .

Крок 4 . x 2 отримує постійну позначку l (x 2 ) = 5 + , p = x 2 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Третя ітерація

Крок 2 . - Тільки вершини x 3 і x 9 мають тимчасові позначки.

;

Крок 3 . відповідає x 8 .

Крок 4 . x 8 отримує постійну позначку l (x 8 ) = 6 + , p = x 8 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Четверта ітерація

Крок 2 . - Ті...льки вершини x 5 , x 6 і x 9 мають тимчасові позначки.

;;

Крок 3 . відповідає x 4 .

Крок 4 . x 4 отримує постійну позначку l (x 4 ) = 7 + , p = x 4 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

П'ята ітерація

Крок 2 . - Тільки вершини x 5 , x 6 і x 3 мають тимчасові позначки.

;;

Крок 3 . відповідає x 9 .

Крок 4 . x 9 отримує постійну позначку l (x 9 ) = 11 + , p = x 9 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Шоста ітерація

Крок 2 . - Тільки вершина x 6 має тимчасову позначку.

Крок 3 . відповідає x 5 .

Крок 4 . x 5 отримує постійну позначку l (x 5 ) = 12 + , p = x 5 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Сьома ітерація

Крок 2 . - Тільки вершина x 6 має тимчасову позначку.

Крок 3 . відповідає x 6 .

Крок 4 . x 6 отримує постійну позначку l (x 5 ) = 17 + , p = x 6 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Восьма ітерація

Крок 2 . - Тільки вершина x 3 має тимчасову позначку.

Крок 3 . x 3 отримує постійну позначку l (x 3 ) = 23 + .

Знайти найкоротші шляхи від вершини 1 до всіх інших вершин графа

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

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 9

x 1

3 2

x 2

5 15 12

x 3

8 24

x 4

6 8 18 4 11

x 5

12 7 20

x 6

20 9 13

x 7

10 4 9 16

x 8

24 16 22

x 9

11 13

Алгоритм працює так:

Крок 1 . .

Перша ітерація

Крок 2 . - Всі позначки тимчасові.

;

Крок 3 . відповідає x 5 .

Крок 4 . x 5 отримує постійну позначку l (x 5 ) = 2 + , p = x 5 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Друга ітерація

Крок 2 . - Всі позначки тимчасові.

;;

Крок 3 . відповідає x 2 .

Крок 4 . x 2 отримує постійну позначку l (x 2 ) = 3 + , p = x 2 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Третя ітерація

Крок 2 . - Тільки вершини x 3 і x 4 мають тимчасові позначки.

;

Крок 3 . відповідає x 3 .

Крок 4 . x 3 отримує постійну позначку l (x 3 ) = 8 + , p = x 3 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Четверта ітерація

Крок 2 . - Всі позначки тимчасові.

;

Крок 3 . відповідає x 4 .

Крок 4 . x 4 отримує постійну позначку l (x 4 ) = 9 + , p = x 4 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

П'ята ітерація

<...p> Крок 2 . - Тільки вершини x 7 , x 6 і x 9 мають тимчасові позначки.

;;

Крок 3 . відповідає x 7 .

Крок 4 . x 7 отримує постійну позначку l (x 7 ) = 13 + , p = x 7 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Шоста ітерація

Крок 2 . - Тільки вершини x 6 і x 8 мають тимчасові позначки.

;

Крок 3 . відповідає x 9 .

Крок 4 . x 9 отримує постійну позначку l (x 9 ) = 20 + , p = x 9 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Сьома ітерація

Крок 2 . - Тільки вершина x 6 має тимчасову позначку.

Крок 3 . відповідає x 6 .

Крок 4 . x 6 отримує постійну позначку l (x 6 ) = 17 + , p = x 6 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Восьма ітерація

Крок 2 . тимчасових позначок немає.

Крок 3 . x 8 отримує постійну позначку l (x 8 ) = 29 + .

Знайти найкоротші шляху від вершини 1 до всіх інших вершин графа.

дискретний математика програма інтерфейс

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 9

x 1

x 2

9

x 3

8 3

x 4

7

x 5

6

x 6

17 4

x 7

4

x 8

7

x 9

9 5

Алгоритм працює так:

Крок 1 . .

Перша ітерація

Крок 2 . - Всі позначки тимчасові.

;

Крок 3 . відповідає x 4 .

Крок 4 . x 4 отримує постійну позначку l (x 4 ) = 7 + , p = x 4 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Друга ітерація

Крок 2 . - Всі позначки тимчасові.

;

Крок 3 . відповідає x 2 .

Крок 4 . x 2 отримує постійну позначку l (x 2 ) = 9 + , p = x 2 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Третя ітерація

Крок 2 .

Крок 3 . відповідає x 7 .

Крок 4 . x 7 отримує постійну позначку l (x 7 ) = 11 + , p = x 7 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Четверта ітерація

Крок 2 .

Крок 3 . відповідає x 8 .

Крок 4 . x 8 отримує постійну позначку l (x 8 ) = 14 + , p = x 8 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

П'ята ітерація

Крок 2 .

Крок 3 . відповідає x 3 .

Крок 4 . x 3 отримує постійну позначку l (x 3 ) = 14 + , p = x 3 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Шоста ітерація

Крок 2 .

Крок 3 . відповідає x 9 .

Крок 4 . x 9 отримує постійну позначку l (x 9 ) = 19 + , p = x 9 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Сьома ітерація

Крок 2 .

Крок 3 . відповідає x 5 .

Крок 4 . x 5 отримує постійну позначку l (x 5 ) = 17 ... + , p = x 5 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Восьма ітерація

Крок 2 .

Крок 3 . x 6 отримує постійну позначку l (x 6 ) = 29 + .

Знайти найкоротші шляхи від вершини 1 до всіх інших вершин графа.

Алгоритм працює так:

Крок 1 . .

Перша ітерація

Крок 2 .

;;

Крок 3 . відповідає x 2 .

Крок 4 . x 2 отримує постійну позначку l (x 2 ) = 5 + , p = x 2 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Друга ітерація

Крок 2 .

;;

Крок 3 . відповідає x 6 .

Крок 4 . x 6 отримує постійну позначку l (x 6 ) = 8 + , p = x 6 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Третя ітерація

Крок 2 .

;;

Крок 3 . відповідає x 4 .

Крок 4 . x 4 отримує постійну позначку l (x 4 ) = 10 + , p = x 4 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Четверта ітерація

Крок 2 .

;

Крок 3 . відповідає x 3 .

Крок 4 . x 3 отримує постійну позначку l (x 3 ) = 13 + , p = x 3 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

П'ята ітерація

Крок 2 .

;

Крок 3 . відповідає x 8 .

Крок 4 . x 8 отримує постійну позначку l (x 8 ) = 16 + , p = x 8 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Шоста ітерація

Крок 2 .

;

Крок 3 . відповідає x 7 .

Крок 4 . x 7 отримує постійну позначку l (x 7 ) = 17 + , p = x 7 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Сьома ітерація

Крок 2 .

;;

Крок 3 . відповідає x 10 .

Крок 4 . x 10 отримує постійну позначку l (x 10 ) = 18 + , p = x 10 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Восьма ітерація

Крок 2 .

Крок 3 . відповідає x 5 .

Крок 4 . x 5 отримує постійну позначку l (x 5 ) = 19 + , p = x 5 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Дев'ята ітерація

Крок 2 .

Крок 3 . x 9 отримує постійну позначку l (x 9 ) = 21 + .

Знайти найкоротші шляхи від вершини 1 до всіх інших вершин графа

Алгоритм працює так:

Крок 1 . .

Перша ітерація

Крок 2 .

;;

Крок 3 . відповідає x 7 .

Крок 4 . x 7 отримує постійну позначку l (x 7 ) = 6 + , p = x 7 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Друга ітерація

Крок 2 .

;

Крок 3 . відповідає x 2 .

Крок 4 . x 2 отримує постійну позначку l (x 2 ) = 7 + , p = x 2 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Третя ітерація

Крок 2 .

;

Крок 3 . відповідає x 4 .

Крок 4 . x 4 отримує постійну позначку l (x 4 ) = 8 + , p = x 4 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Четверта ітерація

Крок 2 .

;;;

Крок 3 . відповідає x 5 .

Крок 4 . x 5 отримує постійну позначку l (x 5 ) = 16 + , p = x 5 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

П'ята ітерація

Крок 2 .

;;

Крок 3 . відповідає x 8 .

Крок 4 . x 8 отримує постійну позначку l (x 8 ) = 16 + , p = x 8 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Шоста ітерація

Крок 2 .

Крок 3 . відповідає x 3 .

Крок 4 . x 3 отримує постійну позначку l (x 3 ) = 18 + , p = x 3 .

Крок 5 . Не всі вершини мають постійні позначки, тому переходимо до кроку 2.

Сьома ітерація

Крок 2 .

Крок 3 . x 6 отримує постійну позначку l (x 6 ) = 20 + .

3. Алгоритмізація задачі

1) Вводимо кількість вершин неорієнтованого графа.

2) Якщо кількість вершин більше 5, то переходимо до пункту 3; інакше переходимо до пункту 4.

3) Генератором випадкових чисел довільно задаються зв'язки між вершинами в матриці смежностей, переходимо до пункту 5.

4) Вводимо зв'язки між вершинами, виходячи з наступної умови:

- якщо не існує шляху довжиною в одне ребро з однієї вершини в іншу, то ставимо В«100В»,

- якщо існує шлях між двома вершинами, то ставимо довільне позитивне ненульове значення ваги дуги.

Всі введені дані заносяться в матрицю смежностей.

5) Вводимо номери вершин, шлях між якими потрібно знайти.

6) Задаємо початкові значення довжин шляхів рівних 100 (в програмі це позначає нескінченність), а позначки всіх вершин обнуляем.

7) Для початкової вершини в матрицю, що зберігає шляху (попередні вершини), заносимо значення нуль, оскільки немає вершин передують початку, значенням шляху присвоюємо значення нуля, помітку на вершину встановлюємо в одиницю.

8) Ізмененяются довжини шляхів між вершинами В«iВ» та початкової за умови, що розглянута дуга не йде з вершини в саму себе і позначка цієї вершини дорівнює нулю, то тоді:

а) переглядаємо довжину шляху в вершину В«iВ» і порівнюємо з довжиною шляху з початкової вершини В«NacВ»

б) отримуємо, що довжина шляху з вершини В«sВ» менше початкового значення шляху в вершину В«iВ», то запам'ятовуємо в T [i] - ом елементі нову довжину шляху (меншу) і H [i] - му присвоюємо значення В«sВ».

9) Присвоюємо змінної 't В» значення 100 (нескінченність), а змінної для зберігання поточної вершини В«kВ» присвоюємо значення нуль.

10) Виробляємо спробу зменшити довжину шляху. Якщо вершина не позначена (її позначка дорівнює нулю), то якщо довжина шляху менше значення В«tВ» то значенням В«tВ» присвоюємо поточне значення шляху, а змінної для зберігання поточної вершини В«kВ» даємо значення цієї змінної.

11) Якщо змінна для зберігання поточної вершини має значення... нуля, то шляху немає, переходимо до пункту 14, інакше переходимо до пункту 12.

12) Якщо змінна для зберігання поточної вершини має значення кінцевої вершини, то шлях знайдений, він найкоротший, переходимо до пункту 14, інакше переходимо до пункту 13.

13) Помітку на вершину, яку зберігає змінна В«kВ», змінюємо на одиницю і переходимо до пункту 8.

14) Виводимо на екран повідомлення про довжину шляху між вершинами, якщо такий шлях існує (тобто шлях має неотрицательную довжину).

4 Екранна форма інтерфейсу та інструкція користувача

Press the first letter of item that you needs

Пункти меню:

1. Алгоритм реалізації поставленого завдання.

2. Зображення вихідного графа.

3. Вихід з програми.

Для вибору пункту необхідно натиснути на відповідну клавішу:

- якщо це пункт 1, то натисніть В«AВ» або В«aВ»;

- якщо це пункт 2, то натисніть В«DВ» або В«dВ»;

- якщо це пункт 3, то натисніть В«EВ» або В«eВ».

Висновок

У відповідності з поставленим завданням в курсовій роботі було виконано наступне:

1) Вивчено конкретний розділ дискретної математики.

2) Вирішені 5 задач з вивченої теми з методичним описом.

3) Розроблено і реалізовано у вигляді програми алгоритм з вивченої теми. Розроблено програмний інтерфейс.

Література

1. Новиков Ф.А. Дискретна математика для програмістів - СПб.: Питер, 2002 рік

1. Немнюгин С.А. Turbo Pascal: практикум - СПб.: Питер, 2002 рік