49210

Знаходження найкоротшого шляху в графі за допомогою алгоритма Дейкстри

Курсовая

Информатика, кибернетика и программирование

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

Украинкский

2013-12-23

241.53 KB

106 чел.

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

Кам'янець-Подільський національний університет імені Івана Огієнка

Кафедра інформатики

КУРСОВА РОБОТА

з дисципліни «Теорія програмування» на тему:

«Знаходження найкоротшого шляху в графі за допомогою алгоритма Дейкстри»

                                       

Студента 3 курсу 34 групи

напряму підготовки 6.040302

Інформатика

Ніколаєва Максима Вікторовича

Керівник:

кандидат фізико-математичних наук, доцент

Власов Віктор Андрійович

Національна шкала ____________

Кількість балів:____Оцінка: ЕСТ8_____

Члени комісії   

___________     Щирба В.С.              

(підпис)              (прізвище та ініціали)

___________     Іванюк В.А.

(підпис)              (прізвище та ініціали)

___________     Власов В.А.

(підпис)             (прізвище та ініціали)

м.Камянець-Подільський – 2013рік

Зміст

Вступ………………………………………………………………………….3

1. Теоретична частина……………………………………………………….4

1.1 Постановка задачі………………………………………......……..4

1.2 Загальні відомості про графи…………………………………….5

1.3 Алгоритм Дейкстри ……….…………………………………….10

1.4 Розгляд алгоритму Дейкстри на прикладі…………………......11

2. Програмна реалізація……………………………………………………15

2.1 Опис алгоритму і структури програми………………………...15

2.2 Опис використаних програмних засобів………………………16

Висновки……………………………………………………………………18

Список використаних джерел…………………………………………......19

Додатки……………………………………………………………………...20

Вступ

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

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

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

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

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

Завдання:

  1.  Дослідити алгоритм Дейкстри.
  2.  Написати програму на мові C#, яка для заданого графа знаходить накоротший шлях між двома заданими внршинами.

  1.  Теоретична частина

1.1 Постановка задачі

Основним завданням даного курсового проекту є програмна реалізація алгоритму пошуку найкоротшого шляху між двома будь-якими вершинами графа.

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

Програма повинна бути реалізована на об’єктно-орієнтованій мові програмування C#.

Дана програма може використовуватися в дискретній математиці для дослідження графів, або в якості наочного посібника, який демонструє застосування алгоритму Дейкстри на практиці.

1.2 Загальні відомості про графи

Графом (неорієнтованим графом) G називається пара множин (V,E ), де E  довільна підмножина множини V (2) (E, V (2)); позначається G =(V,E ).

Елементи множини V називаються вершинами графа G, а елементи множини E  ребрами графа G. Відповідно V називається множиною вершин і E  множиною ребер графа G.

Традиційно ребра {v,w} записуються за допомогою круглих дужок (v,w) (іноді просто vw).

Граф, який складається з однієї вершини, називається тривіальним.

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

Нехай задано граф G =(V,E ). Якщо (v,w)Е, то кажуть, що вершини v i w є суміжними, у противному разі вершини v i w є несуміжними. Якщо е=(v,w)  ребро графа, то вершини v i w називаються кінцями ребра е. У цьому випадку кажуть також, що ребро е з’єднує вершини v i w. Вершина v і ребро е називаються інцидентними, якщо v є кінцем е.

Два ребра називаються суміжними, якщо вони мають спільну вершину.

Існує декілька способів завдання графів.

Одним зі способів завдання графа G =(V,E ) є завдання кожної з множин V і  E за допомогою переліку їх елементів.

Граф G =(V,E ) зручно зображати за допомогою рисунка на площині, який називають діаграмою графа G. Вершинам графа G ставляться у бієктивну відповідність точки площини; точки, що відповідають вершинам v i w, з’єднуються лінією (відрізком або кривою) тоді і тільки тоді, коли v i w суміжні вершини. Зрозуміло, що діаграма графа змінюватиме свій вигляд у залежності від вибору відповідних точок на площині.

Графи можна задавати також за допомогою матриць.

Занумеруємо всі вершини графа G натуральними числами від 1 до n. Матрицею суміжності A графа G називається квадратна
n*n-матриця, в якій елемент aij i-го рядка і j-го стовпчика дорівнює 1, якщо вершини vi та vj з номерами i та j суміжні, і дорівнює 0 у противному разі.

Очевидно, що матриці суміжності графів  симетричні.

Занумеруємо всі вершини графа G числами від 1 до n і всі його ребра  числами від 1 до m. Матрицею інцидентності B графа G називається n*m-матриця, в якій елемент bij i-го рядка і j-го стовпчика дорівнює 1, якщо вершина vi з номером i інцидентна ребру ej з номером j, і дорівнює 0 у противному разі.

Нарешті, ще одним способом завдання графів є списки суміжності. Кожній вершині графа відповідає свій список. У список, що відповідає вершині v, послідовно записуються всі суміжні їй вершини.

Вибір та зручність того чи іншого зі способів завдання графів залежать від особливостей задачі, яка розв’язується.

Граф G1=(V1,E1) називається підграфом графа G =(V,E ), якщо V1=V i E1=E.

Важливі класи підграфів складають підграфи, які отримуються в результаті застосування до заданого графа операції вилучення вершини і/або операції вилучення ребра.

Операція вилучення вершини v з графа G =(V,E ) полягає у вилученні з множини V елемента v, а з множини E  всіх ребер, інцидентних v.

Операція вилучення ребра e з графа G =(V,E )  це вилучення елемента e з множини E. При цьому всі вершини зберігаються.

Графи G1=(V1,E1) і G2=(V2,E2) називаються ізоморфними, якщо існує таке взаємно однозначне відображення множини вершин V1 на множину вершин V2, що ребро (v,w)=E1 тоді і тільки тоді, коли ребро ((v),(w))=E2. Відображення називається ізоморфним відображенням або ізоморфізмом графа G1 на граф G2.

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

Ізоморфне відображення графа G на себе називається автоморфізмом графа G. Автоморфізм графа G =(V,E ), при якому для кожної вершини v V виконується  (v)=v, називається тривіальним автоморфізмом.

Відношення ізоморфізму є відношенням еквівалентності на сукупності графів.

Граф G =(V,E ) називається повним, якщо будь-які дві його вершини суміжні (тобто E=V  (2)). Повний граф з n вершинами позначається Kn.

Очевидно, що будь-яка підстановка множини вершин повного графа Kn є автоморфізмом цього графа. Тому кількість усіх можливих автоморфізмів графа Kn дорівнює n!

Для графів можна означити операції об’єднання, перетину і доповнення.

Об’єднанням графів G1=(V1,E1) і G2=(V2,E2) називається граф G =(V1V2,E1E2); позначається G =G1G2.

Перетином і різницею графів G1=(V,E1) i G2=(V,E2) з однаковими множинами вершин називаються графи G=(V,E1E2) i G=(V,E1\E2) відповідно; позначаються G =G1G2 і G= G1\G2.

Доповненням графа G =(V,E ) називається граф =(V,V (2)\E ). Отже, граф має ту саму множину вершин V, що і граф G, а вершини графа суміжні тоді і лише тоді, коли вони несуміжні в G. Для графа G з n вершинами виконується =Kn\G.

Таким чином можна означити алгебру графів A=<Г,{, ,}> (типу (2,2,1)), носієм якої є множина Г всіх графів. Iснують й інші операції для графів, отже, сигнатуру алгебри A можна розширювати.

Неважко переконатись у справедливості такого твердження.

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

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

Наприклад, у вигляді графа можуть бути зображені:

електричні і транспортні мережі;

інформаційні і комп’ютерні мережі;

карти автомобільних, залізничних і повітряних шляхів, газо- і нафтопроводів;

моделі кристалів;

структури молекул хімічних речовин;

моделі ігор;

різні математичні об’єкти (відношення, частково впорядковані множини, решітки, автомати, ланцюги Маркова, алгоритми і програми тощо);

лабіринти;

плани діяльності або плани виконання певних робіт (розклади);

генеалогічні дерева тощо.

Приклади застосування теорії графів:

пошук зв’язних компонентів у комунікаційних мережах;

пошук найкоротших, “найдешевших” та “найдорожчих” шляхів у комунікаційних мережах;

побудова кістякового дерева:  зв’язність з найменшою можливою кількістю ребер;

пошук максимальної течії для транспортної мережі, в якій визначено вхідні та вихідні вершини та пропускні спроможності ребер;

ізоморфізм графів: ідентичність структур молекул (ізометрія);

знаходження циклів графів:

гамільтонів цикл: обійти всі вершини графа, побувавши в кожній з них лише один раз (задача комівояжера);

ейлерів цикл: обійти всі ребра (контроль дієздатності мережі);

розфарбування графів: розфарбування географічних карт, укладання розкладів, розміщення ресурсів тощо;

планарність графів: проектування друкованих електронних та електричних схем, транспортних розв’язок тощо;

знаходження центрів графа: вершин, максимальна відстань від яких до всіх інших вершин графа є мінімальною (“столиць”)

тощо.

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

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

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

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

Нехай на якомусь кроці вже позначено кілька вершин. Відомі найкоротші шляхи, що ведуть з вихідної вершини до позначених. Для кожної з непозначених вершин проробимо наступне:

1. Розглянемо всі дуги, які ведуть з позначених вершин в одну непозначену. Кожна така дуга є останньою дугою на шляху з вихідної вершини в цю непозанчену.

2. Виберемо з цих шляхів найкоротший. А потім виберемо серед них самий короткий до всіх непозначених вершин, і позначимо вершину, до якої він веде.

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

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

1.4 Розгляд алгоритму Дейкстри на прикладі

Розглянемо виконання алгоритму на прикладі графа зображеного на рисунку 1.1. Неай потрібно знайти відстані від 1-ої вершини до всіх інших. Кружечками позначені вершини, лініями — шляхи між ними («ребра»). Над ребрами позначена їх «вага» — довжина шляху. Надписом над кружечком позначена поточна найкоротша відстань до вершини. На рисунку 1.2 присвоємо мітки всім вершинам.

      Рис. 1.1 – Початковий граф   

Рис. 1.2 – Присвоєння міток всім вершинам

Перший крок. Розглянемо крок алгоритму Дейкстри для нашого прикладу. Мінімальну мітку має вершина 1. Її сусідами є вершини 2, 3 і 6.

Рис. 1.3 – Перший крок

Перший по черзі сусід вершини 1 - вершина 2, тому що довжина шляху до неї мінімальна. Довжина шляху в неї через вершину 1 дорівнює найкоротшій відстані до вершини 1 + довжина ребра, що йде з 1 в 2, тобто 0 + 7 = 7. Це менше поточної мітки вершини 2, тому нова мітка 2-ї вершини дорівнює 7. На графіку спочатку розглянута вершина 3.

Рис. 1.4 – Присвоєння 3-ій вершині нової мітки

Аналогічну операцію проробляємо з двома іншими сусідами 1-ї вершини - 3 і 6.

Рис. 1.5 – Розгляд інших вершин

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

Другий крок. Крок алгоритму повторюється. Знову знаходимо «найближчу» з невідвіданих вершин. Це вершина 2 з міткою 7.

Рис. 1.6 – Перша вершина розглянута

Знову намагаємося зменшити мітки сусідів обраної вершини, намагаючись пройти в них через 2-у. Сусідами вершини 2 є 1, 3, 4.

Перший (по порядку) сусід вершини 2 - вершина 1. Але вона вже переглянута, тому з 1-ю вершиною нічого не робимо.

Наступний сусід вершини 2 - вершина 4. Якщо йти в неї через 2-у, то довжина такого шляху буде = найкоротша відстань до 2 + відстань між вершинами 2 і 4 = 7 + 15 = 22. Встановлюємо мітку вершини 4 рівній 22.

Рис. 1.7 – Розгляд другої вершини

Ще один сусід вершини 2 - вершина 3. Якщо йти в неї через 2, то довжина такого шляху буде = 7 + 10 = 17. Але поточна мітка третьої вершини дорівнює 9 <17, тому мітка не змінюється.

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

Рис. 1.8 – Результат розгляду 2-ї вершини

Третій крок. Повторюємо 2 крок алгоритму, вибравши вершину 3. Після її «обробки» отримаємо такі результати:

Рис. 1.9 – Третій крок

Подальші кроки. Повторюємо 2 крок алгоритму для вершин які залишилися (Це будуть по порядку 6, 4 і 5).

Рис. 1.10 – Подальші кроки

Завершення виконання алгоритму. Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видний на рисунку 1.10: найкоротший шлях від вершини 1 до 2 становить 7, до 3 - 9, до 4 - 20, до 5 - 20, до 6- 11.


  1.  Програмна реалізація
  2.  Опис алгоритму і структури програми

Дана програма розроблена для знаходження мінімального шляху між двома вершинами в графі, який складається з 11, або менше, вершин. Також вона знаходить довжину цього шляху.

Перед запуском програми у файл gragh.txt потрібно ввести ребра графа та їх вагу.

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

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

На рисунку 2.1 показаний загальний алгоритм програми.

  Початок

 

Отримання списку ребер

string[] arcs = File.ReadAllLines("graph.txt");

Створення масиву 11х11

Отримання вершин для відшукання шляху

If (c1==”Q”)

If (c2==”Q”)

                                            Так

Заповнення дистанцій

                          Ні

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

If result > -1

Немає шляху

                                           Ні

Виведення результатів

                          Так

Кінець

Рис. 2.1 – Загальний алгоритм програми

  1.  Опис використаних програмних засобів

Таблиця 2.1 – Опис змінних

Змінна

Тип

Опис

T

static char

Матриця 11х11

arcs

string

Список ребер

L0

int

Масив 11х11

с1

int

Перша вершина

с2

int

Друга вершина

minvalue

int

Мінімальна вага ребра

minnode

int

Вершина яка оброблюється

i, j

int

Лічильники

При написанні програми були використані бібліотеки System, System.IO (простір імен System.IO містить типи, що дозволяють здійснюват читання і запис у файли і потоки даних, а також типи для базової підтримки файлів і папок), System.Collections.Generic (простір імен System.Collections.Generic містить інтерфейси і класи, що визначають універсальні колекції, які дозволяють користувачам створювати типізовані колекції, що забезпечують підвищену продуктивність і безпеку типів у порівнянні з неуніверсальними типізований колекціями), System.Linq (простір імен System.Linq містить класи та інтерфейси, які підтримують запити, які використовують LINQ), System.Text (простір імен System.Text містить класи, що представляють кодування ASCII і Юникод, абстрактні базові класи для перетворення блоків символів в блоки байтів і назад, і клас підтримки, керуючий об'єктами String, і форматуючий такі об'єкти без створення проміжних примірників String), System.Threading.Tasks (простір імен System.Threading.Tasks надає типи, які спрощують роботу з написання паралельного і асинхронного коду).

Також я створив структуру Arc, яка інкапсулює дані про дистанції між вершинами.

Для алгоритму знаходження найкоротшого шляху створив клас Dijkstra, а в ньому методи Dijkstra (для початкової обробки даних отриманих від методу Main), DijkstraSolving (для розрахунку мінімального шляху), та метод Run (передає результат для виведення).

Для обробки вхідних даних та виведення результату виконнання програми я створив клас Program, а в ньому метод Main.

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

Висновки

У даній курсовій роботі розроблена програма, яка реалізує алгоритм Дейкстри. Програма написана на об’єктно-орієнтованій мові C#.  Дана програма може використовуватися в дискретній математиці для дослідження графів, або в якості наочного посібника, який демонструє застосування алгоритму Дейкстри на практиці. Також в процесі написання курсової роботи я детально,  на прикладі, дослідив ефективність застосування алгоритму Дейкстри.


Список використаних джерел

  1.  Бондарев В. М. Основы программирования. / В. М. Бондарев, В. Н. Рублинецкий, Е. Г. Качко – Х. : Фолио, 1998. – 368 с.
  2.  Ковалюк Т. В. Основи програмування. – К. : Видавнича група BHV, 2005. – 384 c.
  3.  Троэлсон Э. C# и платформа .NET 3.0, специальное издание. – СПб. : Питер, 2008. – 1456 с.
  4.  Кармэн Т. Алгоритмы: построение и анализ. / Т. Кармен, Ч. Лейзерсон, Р. Ривест; пер. с англ. А. Шеня – М. : МЦНМО: БИНОМ. Лаборатория знаний, 2004. – 2-е изд., стереотип. – 960 с.
  5.  Харари Ф. Теория графов. / Ф. Харари; пер. с англ. В. П. Козырева – М. : Мир, 1973. – 293 с.
  6.  Вікіпедія: онлайн енциклопедія. – https://uk.wikipedia.org
  7.  Microsoft Developer Network. – http://msdn.microsoft.com 
  8.  IBM developerWorks : Ресурс IBM для разработчиков и IT профессионалов. – https://www.ibm.com/developerworks/ru/

Додатки

Додаток 1.

Лістинг програми

using System;

using System.IO;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

struct Arc

{

   public int Start;

   public int Finish;

   public int Distance;

   public Arc(int start, int finish, int distance)

   {

       Start = start;

       Finish = finish;

       Distance = distance;

   }

}

class Dijkstra

{

   private int rank = 0;

   private int[,] L;

   private int[] C;

   public int[] D;

   public List<Arc>[] P;

   private int trank = 0;

   public Dijkstra(int paramRank, int[,] paramArray)

   {

       L = new int[paramRank, paramRank];

       C = new int[paramRank];

       D = new int[paramRank];

       P = new List<Arc>[paramRank];

       rank = paramRank;

       for (int i = 0; i < rank; i++)

       {

           P[i] = new List<Arc>();

           for (int j = 0; j < rank; j++)

           {

               L[i, j] = paramArray[i, j];

           }

       }

       for (int i = 0; i < rank; i++)

       {

           C[i] = i;

       }

       C[0] = -1;

       for (int i = 0; i < rank; i++)

       {

           if (i > 0) D[i] = L[0, i];

           if (D[i] >= 0)

           {

               Arc arc = new Arc(0, i, D[i]);

               P[i].Add(arc);

           }

       }

   }

   public void DijkstraSolving()

   {

       int minValue = Int32.MaxValue;

       int minNode = 0;

       for (int i = 0; i < rank; i++)

       {

           if (C[i] == -1) continue;

           if (D[i] > 0 && D[i] < minValue)

           {

               minValue = D[i];

               minNode = i;

           }

       }

       C[minNode] = -1;

       for (int i = 0; i < rank; i++)

       {

           if (L[minNode, i] < 0) continue;

           if (D[i] < 0)

           {

               D[i] = minValue + L[minNode, i];

               P[i] = P[minNode].GetRange(0, P[minNode].Count);

               Arc arc = new Arc(minNode, i, L[minNode, i]);

               P[i].Add(arc);

               continue;

           }

           if ((D[minNode] + L[minNode, i]) < D[i])

           {

               D[i] = minValue + L[minNode, i];

               P[i] = P[minNode].GetRange(0, P[minNode].Count);

               Arc arc = new Arc(minNode, i, L[minNode, i]);

               P[i].Add(arc);

           }

       }

   }

   public void Run()

   {

       for (trank = 1; trank < rank; trank++)

       {

           DijkstraSolving();

       }

   }

}

class Program

{

   // Матрица

   static char[,] T =

{

{'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'},

{'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'A'},

{'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'A', 'B'},

{'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'A', 'B', 'C'},

{'E', 'F', 'G', 'H', 'I', 'J', 'K', 'A', 'B', 'C', 'D'},

{'F', 'G', 'H', 'I', 'J', 'K', 'A', 'B', 'C', 'D', 'E'},

{'G', 'H', 'I', 'J', 'K', 'A', 'B', 'C', 'D', 'E', 'F'},

{'H', 'I', 'J', 'K', 'A', 'B', 'C', 'D', 'E', 'F', 'G'},

{'I', 'J', 'K', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'},

{'J', 'K', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'},

{'K', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'}

};

   static void Main()

   {

       // получение списка дуг

       string[] arcs = File.ReadAllLines("graph.txt");

       // создание массива 11 X 11

       int[,] L0 = new int[11, 11];

       for (int i = 0; i < 11; i++)

       {

           for (int j = 0; j < 11; j++)

           {

               L0[i, j] = -1;

           }

       }

       // расчеты

       Console.Clear();

       Console.WriteLine(" Для выхода нажимаем Q.\n");

       while (true)

       {

           // получение вершин

           char c1, c2;

           do

           {

               Console.Write(" Ввести первую вершину графа от A до K : ");

               c1 = Console.ReadLine().ToUpper()[0];

               if (c1 == 'Q') return;

           }

           while (!(c1 >= 'A' && c1 <= 'K'));

           do

           {

               Console.Write(" Ввести вторую вершину графа от A до K : ");

               c2 = Console.ReadLine().ToUpper()[0];

               if (c2 == 'Q') return;

           }

           while (!(c2 >= 'A' && c2 <= 'K'));

           int[,] L = (int[,])L0.Clone();

           Dictionary<char, int> dict = new Dictionary<char, int>();

           Dictionary<int, char> dict2 = new Dictionary<int, char>();

           int index = (int)c1 - 65;

           for (int i = 0; i < 11; i++)

           {

               dict.Add(T[index, i], i);

               dict2.Add(i, T[index, i]);

           }

           // заполнение дистанций

           foreach (string arc in arcs)

           {

               string[] items = arc.Split(',');

               int x = dict[items[0][0]];

               int y = dict[items[1][0]];

               int dist = int.Parse(items[2]);

               L[x, y] = dist;

               L[y, x] = dist;

           }

           // создание и инициализация объекта Дейкстры

           Dijkstra dijk = new Dijkstra(11, L);

           // вывод результата

           dijk.Run();

           int result = dijk.D[dict[c2]];

           if (result > -1)

           {

               Console.WriteLine("\n Самая краткая дистанция от {0} до {1} = {2}\n", c1, c2, result);

               Console.WriteLine("\n Путь : \n");

               foreach (Arc arc in dijk.P[dict[c2]])

               {

                   Console.WriteLine(" {0} -> {1} = {2}", dict2[arc.Start], dict2[arc.Finish], arc.Distance);

               }

               Console.WriteLine();

           }

           else

           {

               Console.WriteLine("\n Пути от вершины {0} до вершины {1} не существует!\n", c1, c2);

           }

       }

   }

}

Додаток 2

Результат виконання програми

Додаток 3

Файл graph.txt


 

А также другие работы, которые могут Вас заинтересовать

57626. Урок позакласного читання «Little Red Riding Hood» 214.5 KB
  Мета: ввести нові лексичні одиниці: a wood, a woodcutter, a basket, a cake to see, to hear, to smell, to shout; повторити правила читання буквосполучень: оо, sh, ou, ea; розвивати навички читання та усного мовлення;
57627. Round the calendar. My favourite holiday 58 KB
  Today we shall speak about different holidays in Ukraine and Britain. We shall do exercises, sing, listen to a very interesting tale. So, you must be active, careful and try to get good marks for the lesson.
57628. Свята. День народження 47.5 KB
  Children, I want you to guess the topic of our lesson. I’ll read the sentences and your task is to finish them with the right words: ball, rabbit, teacher, ice cream, day-books, holiday, yellow, autumn.
57629. I, My Family, Friends, Traits of Character 349.5 KB
  Цели: Развитие речевой компетенции в монологической диалогической речи; учить учащихся говорить на уровне 1-2-3 предложений. Учить учащихся выражать свою точку зрения; активизация лексических знаний по теме и подтеме
57630. Євро 2012: перспективи та виклики 571.5 KB
  Objectives: to introduce the topic, to work with vocabulary related to the world of sport, countries their location, features, people and culture; to read for detailed comprehension...
57631. Family relationship 59.5 KB
  I suppose this topic will be interesting for you, because family is very important in the life of any person, isn’t it. So, today we’ll learn more about relationship between children and parents, have a discussion, learn some new vocabulary, do some exercises to remember them better, read a text.
57632. Сім’я та друзі 30.5 KB
  Мета: узагальнити та систематизувати лексичні одиниці по темі «Сім’я та друзі». Застосовувати мовні вміння на практиці, розвивати комунікативні навички, монологічне та діалогічне мовлення...
57634. Особенности кредитования предприятий оптовой и розничной торговли в ООО Банк «Элита» 150.65 KB
  Кредитные операции – это отношения между кредитором и дебитором (заемщиком) по поводу предоставления (получения) во временное пользование денежных средств, их возврата и оплаты.