Розробка програмних продуктів на основі сучасних платформ програмування

Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ ТРАНСПОРТНИЙ УНІВЕРСИТЕТ

Факультет транспортних та інформаційних технологій

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

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

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

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

Виконав: Сісьомка А.В.

Науковий керівник: Москаленко Н.В.

Київ 2014

ЗМІСТ

ВСТУП

1. АНАЛІЗ ПРЕДМЕТНОЇ ОБЛАСТІ. ПОСТАНОВКА ЗАДАЧІ

1.1 ЗАГАЛЬНІ ВІДОМОСТІ

1.2 ПОСТАНОВКА ЗАДАЧІ

2. РОЗРОБКА СХЕМ АЛГОРИТМІВ

2.1 ЗАДАЧА ПРО НАЙКОРОТШИЙ ШЛЯХ

2.1.1 АЛГОРИТМ ДЕЙКСТРИ

2.1.2 АЛГОРИТМ ФЛОЙДА

2.1.3 МАТРИЧНИЙ МЕТОД

2.1.4 МОДИФІКОВАНИЙ АЛГОРИТМ ДЕЙКСТРИ

3. ОПИС ВИКОРИСТАННЯ НА ПРАКТИЦІ

ВИСНОВОК

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

ДОДАТОК



ВСТУП

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

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

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

· алгоритм Дейкстри (використовується для знаходження оптимального маршруту між двома вершинами);

· алгоритм Флойда (для знаходження оптимального маршруту між усіма парами вершин);

· матричний метод;

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

РОЗДІЛ 1. АНАЛІЗ ПРЕДМЕТНОЇ ОБЛАСТІ. ПОСТАНОВКА ЗАДАЧІ

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

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

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

Найбільший інтерес з перерахованих типів представляють перші три, причому перші два з них реалізуються за допомогою різновидів алгоритму

Дейкстри, а третій за допомогою алгоритму Флойда.

1.1 ОСНОВНІ ВИЗНАЧЕННЯ ТЕОРІЇ ГРАФІВ

Граф -- це сукупність об'єктів із зв'язками між ними.

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

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

Граф або неорієнтований граф -- це впорядкована пара

,

для якої виконуються наступні умови:

-- множина вершин або вузлів,

-- множина пар (у випадку неорієнтованого графу -- невпорядкованих) вершин, які називають ребрами.

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

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

1.2 ПОСТАНОВКА ЗАДАЧІ

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

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

Розробка програмного комплексу, яка чотирма методами вирішує задачу визначення найкоротших маршрутів у середовищі заданого орієнтованого графа (рис. 1.1).

Перший метод Дейкстри знаходить найкоротші маршрути від заданої вершини до всіх інших;

другий метод Флойда;

третій матричний метод визначають найкоротші маршрути між будь-якою парою вершин;

четвертий модифікований метод Дейкстри;

2. РОЗРОБКА СХЕМ АЛГОРИТМІВ

2.1 ЗАДАЧА ПРО НАЙКОРОТШИЙ ШЛЯХ

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

Формально, маємо зважений граф (це набір вершин V і ребер E з дійсно-значимою функцією ваги f : E > R), і заданим елементом v з V, знайти шлях P з v до v' з V такий, що

найменша серед усіх шляхів, що зв'язують v з v' .

2.1.1 АЛГОРИТМ ДЕЙКСТРИ

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

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

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

2.1.2 АЛГОРИТМ ФЛОЙДА

Припустимо, що ми маємо позначений орграф, що містить час польоту по маршрутах, що зв'язує визначені міста, і ми хочемо побудувати таблицю, де приводився б мінімальний час перельоту з одного (довільного) міста в будь-який іншій. У цьому випадку ми зіштовхуємося з загальною задачею пошуку найкоротших шляхів, тобто перебуванням найкоротших шляхів між усіма парами вершин орграфа. Більш строге формулювання цієї задачі наступне: є граф G = (V, Е), кожній дузі v --> w цього графа зіставлена позитивна вартість C[v, w]. Загальна задача перебування найкоротших шляхів полягає в пошуку для кожної упорядкованої пари вершин (v, w) будь-якого шляху від вершини v до вершини w, довжина якого мінімальна серед усіх можливих шляхів від v до w. Можна вирішити цю задачу, послідовно застосовуючи алгоритм Дейкстри для кожної вершини, що повідомляється як джерело. Але існує прямий спосіб рішення даної задачі, що використовує алгоритм Флойда (Floyd). Для визначеності покладемо, що вершини графа послідовно пронумеровані від 1 до п. Алгоритм Флойда використовує матрицю А розміру п х п, у якій обчислюються довжини найкоротших шляхів. Спочатку A[i,j] = C[i, j] для всіх i № j. Якщо дуга i --> j відсутня, то C[i, j] = Ґ (нескінченності). Кожен діагональний елемент матриці А дорівнює 0.

Над матрицею А виконується п ітерацій. Після k-й ітерації A[i, j] містить значення найменшої довжини шляху з вершини i у вершину j, що не проходять через вершини з номером, більшим ніж k. Іншими словами, між кінцевими вершинами шляху i і j можуть знаходитися тільки вершини, номера яких менше k. На k-й ітерації для обчислення матриці А застосовується наступна формула:

Аk [i,j] = min(Ak-1[i,j], Ak-1[i,k] +Ak-1[k,j]).

Нижній індекс k позначає значення матриці А після k-й ітерації, але це не означає, що існує п різних матриць, цей індекс використовується для скорочення запису. Графічна інтерпретація цієї формули показана на рис. 2.

Рис. 2. Включення вершини k у шлях від вершини i до вершини j

Для обчислення Ak[i, j] проводиться порівняння величини Ak-1[i, j] (тобто вартість шляху від вершини i до вершини j без участі вершини k чи іншої вершини з більш високим номером) з величиною Ak-1[i, k] + Ak-1[k, j] (вартість шляху від вершини i до вершини k плюс вартість шляху від вершини k до вершини j). Якщо шлях через вершину k дешевше, ніж Ak-1[i, j], то величина Ak[i, j] змінюється.

2.1.3 МАТРИЧНИЙ МЕТОД

Спочатку складається матриця суміжності S вже відомого нам графа G = (V, Е), зображеного на рис. 1. Рядки матриці S відповідають вершинам Vi (i =1,5) ,стовпці - вершинам Vj ( j =1,5) . Елемент Sij , що стоїть на перетинанні i-го рядка й j-го стовпця, покладається рівним 1 при наявності прямого зв'язку (дуги Eij) між вершинами Vi й Vj і 0 - при відсутності такого зв'язку

Далі визначається матриця S2 = S + S за наступним правилом додавання елементів матриць S:

При знаходженні матриці r-ї використовують такі ж операції:

,

елементи якої:

Розрахунок матриці закінчується, якщо в процесі розрахунку матриці виконується рівність

Елементи матриці , розрахунок закінчуємо.

Елементи матриці визначають довжину найкоротшого шляху між вершинами V_i і V_j, що містить m ланок (дуг).

У процесі формування матриць одержуємо матрицю P, елементи якої являють собою кількості дуг, що складають найкоротші шляхи між вершинами V_i і V_j графа G.

2.1.4 МОДИФІКОВАНИЙ МЕТОД ДЕЙКСТРИ

Модифікація алгоритму полягає в тому, що на початковому етапі вибираються і

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

РОЗДІЛ 3. ОПИС ВИКОРИСТАННЯ НА ПРАКТИЦІ

На цьому етапі нам потрібно знайти найкоротші шляхи чотирма способами.

Рис.1. Головне вікно програми

Натискаємо «Сформувати» і нам виводить матрицю по заданому графу.

Рис.2. Вивід матриці

Вводимо початкову і кінцеві вершини графа і натискаємо на перший метод «Метод Дейсктри».



Рис.3. Метод Дейкстри

Продовжуємо далі натискати на методи.

Рис.4. Метод Флойда



Рис.5. Модифікований метод Дейсктри або метод графів

Рис.6.

ВИСНОВОК

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

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

програмування математичний граф матричний

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

1. Бурков В.Н., Горгидзе И.А., Ловецкий С.Е. Прикладные задачи теории графов. Тбилиси: Мецниереба, 1974. - 234 с.

2. Бурков В.Н., Ланда Б. Д., Ловецкий С.Е., Тейман А.И., Чернышев В.Н. Сетевые модели и задачи управления.М.: Советское радио, 1967. - 144 с.

3. Вагнер Г. Основы исследования операций. М.: Мир, 1972. Т. 1-4.

4. Воронин А.А., Мишин С.П. Оптимальные иерархические структуры. М.: ИПУ РАН, 2003. - 210 с.

5. Глинський Я.М., Анохін В.Є., Ряжська В.А. C++ і C++ Builder. Навч. посіб. 2-е вид. - Львів: Деол, СПД Глинський, 2004. - 192 с.

6. Емеличев В.А,, Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. - 384 с.

7. Климова Л.М. Основы практического программирования на языке Си++. - М.: Приор, 2003. - 464 с.

8. Коргин Н.А. Механизмы обмена в активных системах. М.: ИПУ РАН, 2003.

9. Методичні вказівки до виконання курсової роботи з дисципліни "Новітні платформи програмування" для студентів спеціальності 7.080401 "Інформаційні управляючі системи та технології" / Укл. Н.В. Москаленко, Н.В. Кірхар, Київ, НТУ, 2011

10. Новиков Д.А. Сетевые структуры и организационные системы. М.: ИПУ РАН, 2003. - 102 с.

11. Прокудін Г. С., Білоус С. О. Один з підходів до вирішення сітьової транспортної задачі. // Безпека дорожнього руху України. - К.: ООО "Журнал "Радуга", 2003, № 1 - 2(15). - С. 52 - 56.

ДОДАТОК

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using System.Drawing.Drawing2D;

namespace Курсовая

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

}

// Переменные

int n; // количество вершин

Point[] V; // Массив точек, где находятся центы вершин при отрисовки

int D; // Диаметр вершины при отрисовки

int? [,] R;

List<List<int>> Route;

bool [] ANode; // Начальные точки, проверка отметки

bool[] BNode; // Конечные точки, проверка отметки

private void panel1_Paint(object sender, PaintEventArgs e)

{

}

private void Form1_Load(object sender, EventArgs e)

{

n = 6;

ANode = new bool[n]; // начальные точки

BNode = new bool[n]; // конечные точки

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

{

ANode[i] = false; // CheckBox не отмечены

BNode[i] = false;

}

Route = new List<List<int>>(0);

V = new Point[n]; // масив вершин

D = 40; // Диаметр вершины

int x = pictureBoxOUT.ClientSize.Width / 2, y = pictureBoxOUT.ClientSize.Height / 2; // становимся в центр экрана

int angle = 18, r = 140; // угол наклонения звезды

Point p = new Point();

// строим точки в ввиде звезды и заполняем масив V

p.X = (int)(x + r * Math.Cos((angle + 1 * 72) * Math.PI / 180));

p.Y = (int)(y - r * Math.Sin((angle + 1 * 72) * Math.PI / 180));

V[0] = p;

p.X = (int)(x + r * Math.Cos((angle + 2 * 72) * Math.PI / 180));

p.Y = (int)(y - r * Math.Sin((angle + 2 * 72) * Math.PI / 180));

V[1] = p;

p.X = x;

p.Y = y;

V[2] = p;

p.X = (int)(x + r * Math.Cos((angle + 0 * 72) * Math.PI / 180));

p.Y = (int)(y - r * Math.Sin((angle + 0 * 72) * Math.PI / 180));

V[3] = p;

p.X = (int)(x + r * Math.Cos((angle + 3 * 72) * Math.PI / 180));

p.Y = (int)(y - r * Math.Sin((angle + 3 * 72) * Math.PI / 180));

V[4] = p;

p.X = (int)(x + r * Math.Cos((angle + 4 * 72) * Math.PI / 180));

p.Y = (int)(y - r * Math.Sin((angle + 4 * 72) * Math.PI / 180));

V[5] = p;

R = new int?[n, n]; // двумерный масив

}

public Point[] getRoutePoint(int a, int b)

{

double L = Math.Pow((Math.Pow(V[b].X - V[a].X, 2) + Math.Pow(V[b].Y - V[a].Y, 2)), 1.0 / 2); // длина линии между точками

double angle = Math.Acos((V[b].X - V[a].X) / L); // угол под которым строить линию

Point[] p = new Point[2];

p[0].X = (int)(V[a].X + (D / 2) * Math.Cos(angle)); // точка Х на круге вершины с котрой начинаем строить линию

p[1].X = (int)(V[a].X + (L - D / 2) * Math.Cos(angle)); // точка Х на круге другой вершины

if (V[a].Y > V[b].Y)

{

p[1].Y = (int)(V[a].Y - (L - D / 2) * Math.Sin(angle)); // точка Y на круге второй вершины

p[0].Y = (int)(V[a].Y - (D / 2) * Math.Sin(angle)); // точка Y на круге первой вершины

}

else

{

p[1].Y = (int)(V[a].Y + (L - D / 2) * Math.Sin(angle));

p[0].Y = (int)(V[a].Y + (D / 2) * Math.Sin(angle));

}

return p; // масив из двух точек

}

public Point getRouteValuePoint(int a, int b)

{

double L = Math.Pow((Math.Pow(V[b].X - V[a].X, 2) + Math.Pow(V[b].Y - V[a].Y, 2)), 1.0 / 2); // длина линии

double angle = Math.Acos((V[b].X - V[a].X) / L);

Point p = new Point();

// нахождение точки между вдумя точками p0 и p1 для подписи длины

p.X = (int)(V[a].X + L/2 * Math.Cos(angle));

if (V[a].Y > V[b].Y)

p.Y = (int)(V[a].Y - L / 2 * Math.Sin(angle));

else

p.Y = (int)(V[a].Y + L / 2 * Math.Sin(angle));

return p;

}

private void pictureBoxOUT_Paint(object sender, PaintEventArgs e)

{

Pen p = new Pen(Color.Black, 2); // цвет и толщина ручки

Font f = new Font("Arial", 14); // шрифт

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

{

bool find = false;

for (int j = 0; j < Route.Count && find == false; j++)

{

for (int k = 0; k < Route[j].Count; k++)

if(Route[j][k] == i) // если точка принадлежит маршруту

{

if(ANode[i] == true) // если точка является начальной

p.Color = Color.Green; // то становится зеленой

else if (BNode[i] == true) // точка является конечной

p.Color = Color.Red; // то становится красной

else

p.Color = Color.Orange; // если точка является промежуточной

find = true; // то становится оранжевой

break;

}

else

p.Color = Color.Black; // если точка не является ни начальной, ни конечной, ни промежуточной то становится черной

}

e.Graphics.DrawEllipse(p, V[i].X - D / 2, V[i].Y - D / 2, D, D); // круг вокруг вершин

SizeF size = e.Graphics.MeasureString((i + 1).ToString(), f);

e.Graphics.DrawString((i + 1).ToString(), f, new SolidBrush(Color.Black), V[i].X - size.Width / 2, V[i].Y - size.Height/2); // подписывем вершины

}

p.CustomEndCap = new AdjustableArrowCap(4.0F, 8.0F); // наклонение стрелки

// находим если линия пренадлежить маршруту

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

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

if (R[i, j] != null)

{

bool find = false;

for (int l = 0; l < Route.Count && find == false; l++)

{

for (int k = 0; k < Route[l].Count-1; k++)

if (Route[l][k] == j && Route[l][k+1] == i)

{

find = true; // если принадлежит

break;

}

}

if (find == true)

p.Color = Color.Orange; // то становится оранжевой

else

p.Color = Color.Black; // если нет то черной

Point[] points = getRoutePoint(i, j);

e.Graphics.DrawLine(p, points[0], points[1]); // перекрашиваем линию в цвет p

}

Font f2 = new Font("Arial", 10,FontStyle.Bold); // стиль и шрифт

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

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

if (R[i, j] != null)

{

SizeF s = e.Graphics.MeasureString((i + 1).ToString(), f);

Point point = getRouteValuePoint(i, j); // точка на центре линии

e.Graphics.DrawString(R[i, j].ToString(), f2, new SolidBrush(Color.Red), point.X - s.Width / 2, point.Y - s.Height / 2);

}

}

//__________________

// Матричный метод

static int sump(int ind1, int ind2, int i, int j, int?[, ,] SS) // сума маршрутов через точку

{

int? min = null; int?[] SUM = new int?[SS.GetLength(1)];

for (int k = 0; k < SS.GetLength(1); k++)

if (SS[ind1, i, k] != 0 && SS[ind2, k, j] != 0)

{

SUM[k] = SS[ind1, i, k] + SS[ind2, k, j];

}

else

SUM[k] = null;

for (int k = 0; k < SS.GetLength(1); k++)

if (min == null || SUM[k] < min)

min = SUM[k];

if (min == null) min = 0;

return (int)min;

}

// поиск минимального маршрута

static int? minC(int i, int j, int?[, ,] SS, int bol)

{

int?[] MIN = new int?[SS.GetLength(1)]; int? min, p;

for (int k = 0; k < SS.GetLength(1); k++)

if (SS[k, i, j] != 0)

MIN[k] = SS[k, i, j];

else

MIN[k] = null;

min = null;

p = null;

for (int k = 0; k < SS.GetLength(1); k++)

if ((MIN[k] < min) || (min == null && MIN[k] != null))

{

min = MIN[k];

p = k;

}

if (bol == 0)

return min;

else return p;

}

void Matrix()

{

int n = R.GetLength(1);

int?[,] P = new int?[n, n];

int?[,] D = new int?[n, n];

int?[, ,] S = new int?[n, n, n];

// присваивание значений маршрутов

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

{

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

{

if (R[i, j] != null)

S[0, i, j] = R[i, j];

else

S[0, i, j] = 0;

P[i, j] = 0;

}

S[0, i, i] = 0;

}

for (int k = 0; k < n - 1; k++)

{

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

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

{

S[k + 1, i, j] = sump(0, k, i, j, S);

}

}

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

{

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

{

D[i, j] = minC(i, j, S, 0);

P[i, j] = minC(i, j, S, 1);

}

}

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

{

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

{

if (D[i, j] != null && i != j && ANode[i] == true && BNode[j] == true)

{

List<int> OUT = new List<int>();

OUT.Add(i); // вектор коротких маршрутов

if (S[0, i, j] == D[i, j])

OUT.Add(j);

else

{

int i1 = i;

int min_i = 0;

for (int t = (int)(P[i1, j] - 1); t >= 0 && P[i1, j] != null; t--)

{

int? min = null;

for (int k = 0; k < n; k++)

{

if ((S[0, i1, k] * S[t, k, j]) != 0)

{

if (((S[0, i1, k] + S[t, k, j]) < min || (min == null)) && S[0, i1, k] != null && S[t, k, j] != null)

{

min = (S[0, i1, k] + S[t, k, j]);

min_i = k;

}

}

}

OUT.Add(min_i);

i1 = min_i;

}

OUT.Add(j);

}

OUT.Reverse();

Route.Add(OUT);

}

}

}

}

//__________________

List<int> rVertexFather(int pstart, int pend, int?[] pVF)

{

List<int> Out = new List<int>(1); // создает вектор Out

Out.Add(pend); // 1 элемент

if (pend != pstart && pVF[pend] != null)

{

List<int> rOutput = rVertexFather(pstart, (int)pVF[pend], pVF);

Out.AddRange(rOutput);

}

return Out;

}

void Dijkstra(int a) // метод Дейкстры

{

bool[] P = new bool[R.GetLength(1)];

int?[] pVertexFather = new int?[R.GetLength(1)];

for (int i = 0; i < R.GetLength(1); i++)

P[i] = false;

P[a] = true;

List<int> pQueue = new List<int>();

pQueue.Add(a);

int?[] D = new int?[R.GetLength(1)];

for (int i = 0; i < R.GetLength(1); i++)

{

if (i == 0)

for (int j = 0; j < R.GetLength(1); j++)

{

D[j] = R[pQueue[pQueue.Count - 1], j];

if (D[j] != null)

pVertexFather[j] = pQueue[pQueue.Count - 1];

}

else

for (int j = 0; j < R.GetLength(1); j++)

if (!P[j] && (D[pQueue[pQueue.Count - 1]] + R[pQueue[pQueue.Count - 1], j] < D[j] || (D[j] == null && R[pQueue[pQueue.Count - 1], j] != null)))

{

D[j] = D[pQueue[pQueue.Count - 1]] + R[pQueue[pQueue.Count - 1], j];

pVertexFather[j] = pQueue[pQueue.Count - 1];

}

int? min = null;

for (int j = 0; j < R.GetLength(1); j++)

{

if (!P[j] && D[j] != null)

{

if (min == null || D[j] < D[(int)min])

min = j;

}

}

if (min == null)

break;

pQueue.Add(Convert.ToInt32(min));

P[Convert.ToInt32(min)] = true;

}

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

{

if (D[j] != null && BNode[j] == true )

{

Route.Add(rVertexFather(a, j, pVertexFather));

}

}

}

//__________________

// метод Флойда

static List<int> floyd_vyvod(int x, int y, int?[,] P)

{

List<int> Out = new List<int>(0);

if (P[x, y] > 0)

{

Out.AddRange(floyd_vyvod(x, (int)P[x, y], P));

Out.Add((int)(P[x, y]));

Out.AddRange(floyd_vyvod((int)P[x, y], y, P));

}

return Out;

}

void Floyd()

{

int?[,] rVertex = new int?[n, n];

int?[,] A = new int?[n,n];

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

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

{

if (i != j)

{

A[i, j] = R[i, j];

}

else A[i, j] = 0;

rVertex[i, j] = 0;

}

for (int k = 0; k < n; k++)

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

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

if (A[i, j] > A[i, k] + A[k, j] || (A[i, j] == null && A[k, j] != null && A[i, k] != null))

{

A[i, j] = A[i, k] + A[k, j];

rVertex[i, j] = k;

}

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

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

if ((i != j) && (A[i, j] != null))

if(ANode[i] ==true && BNode[j] ==true)

{

List<int> Out = new List<int>(0);

Out.Add(i);

Out.AddRange(floyd_vyvod(i, j, rVertex));

Out.Add(j);

Out.Reverse();

Route.Add(Out);

}

}

private void buttonLoadDataV_Click(object sender, EventArgs e)

{

// маршруты

R[0, 2] = 30;

R[0, 5] = 10;

R[0, 3] = 100;

R[1, 2] = 80;

R[1, 4] = 50;

R[2, 3] = 40;

R[2, 5] = 10;

R[3, 5] = 69;

R[5, 4] = 20;

R[4, 2] = 70;

R[4, 1] = 50;

// очистка

dataGridViewRoutes.Columns.Clear();

dataGridViewRoutes.Rows.Clear();

// создание заголовков

DataGridViewTextBoxColumn head = new DataGridViewTextBoxColumn();

head.HeaderText = "";

head.Name = "Node";

head.SortMode = System.Windows.Forms.DataGridViewColumnSortMode.NotSortable;

head.ReadOnly = true;

dataGridViewRoutes.Columns.Add(head);

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

{

dataGridViewRoutes.Rows.Add();

dataGridViewRoutes.Rows[i].Cells[0].Value = (i + 1).ToString(); ; // нумерация строк

dataGridViewRoutes.Rows[i].Cells[0].Style.BackColor = System.Drawing.SystemColors.Control;

}

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

{

DataGridViewTextBoxColumn h = new DataGridViewTextBoxColumn();

h.HeaderText = (i+1).ToString(); // нумерация столбцов

h.Name = "Colum" + i.ToString();

h.SortMode = System.Windows.Forms.DataGridViewColumnSortMode.NotSortable;

dataGridViewRoutes.Columns.Add(h);

}

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

{

for (int j = 0; j < R.GetLength(1); j++)

{

dataGridViewRoutes.Rows[i].Cells[j + 1].Value = R[i, j]; // заполнение матрицы значениями маршрутов

}

}

pictureBoxOUT.Invalidate();

}

private void buttonFloyd_Click(object sender, EventArgs e)

{

Route.Clear();

if (!fValidate())

{

pictureBoxOUT.Invalidate();

return;

}

Floyd();

pictureBoxOUT.Invalidate();

richTextBoxOut.Text += "\n\tМетод Флойда\n\n";

for (int i = 0; i < Route.Count; i++)

{

int? sum = 0;

String str = "";

List<int> buff = new List<int>();

buff = Route[i].ToList(); // добавление Route[i] в baff

buff.Reverse(); // обратный порядок

for (int j = 1; j < buff.Count; j++)

{

sum += R[buff[j - 1], buff[j]];

}

for (int j = buff.Count - 1; j >= 0; j--)

if (j != Route[i].Count - 1)

str += " -> " + (Route[i][j] + 1).ToString();

else

str += (Route[i][j] + 1).ToString();

str += " = " + sum + "\n";

richTextBoxOut.Text += str;

}

}

private void buttonMatrix_Click(object sender, EventArgs e)

{

Route.Clear();

if (!fValidate())

{

pictureBoxOUT.Invalidate();

return;

}

Matrix();

pictureBoxOUT.Invalidate();

richTextBoxOut.Text += "\n\tМатричний метод\n\n";

for (int i = 0; i < Route.Count; i++)

{

int? sum = 0;

String str = "";

List<int> buff = new List<int>();

buff = Route[i].ToList();

buff.Reverse();

for (int j = 1; j < buff.Count; j++)

{

sum += R[buff[j - 1], buff[j]];

}

for (int j = buff.Count - 1; j >= 0; j--)

if (j != Route[i].Count - 1)

str += " -> " + (Route[i][j] + 1).ToString();

else

str += (Route[i][j] + 1).ToString();

str += " = " + sum + "\n";

richTextBoxOut.Text += str;

}

}

private void buttonDijkstra_Click(object sender, EventArgs e)

{

Route.Clear();

if (!fValidate())

{

pictureBoxOUT.Invalidate();

return;

}

int count = 0;

int num = 0;

for (int i = 0; i < n && count <2; i++)

if (ANode[i] == true)

{

count++;

num = i;

}

if(count == 1)

Dijkstra(num);

pictureBoxOUT.Invalidate();

richTextBoxOut.Text += "\n\tМетод Дейкстри\n\n";

for(int i=0; i<Route.Count; i++)

{

int? sum = 0;

String str = "";

List<int> buff = new List<int>();

buff = Route[i].ToList();

buff.Reverse();

for (int j = 1; j < buff.Count; j++)

{

sum += R[buff[j-1], buff[j]];

}

for (int j = buff.Count - 1; j >= 0; j--)

if (j != Route[i].Count - 1)

str +=" -> "+ (Route[i][j]+1).ToString();

else

str += (Route[i][j]+1).ToString();

str +=" = "+sum + "\n";

richTextBoxOut.Text += str;

}

}

// метод графов

private void buttonNEW_Click(object sender, EventArgs e)

{

Route.Clear();

if (!fValidate())

{

pictureBoxOUT.Invalidate();

return;

}

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

if (ANode[i] == true)

{

Dijkstra(i);

}

pictureBoxOUT.Invalidate();

richTextBoxOut.Text += "\n\tМетод Графів\n\n";

for (int i = 0; i < Route.Count; i++)

{

int? sum = 0;

String str = "";

List<int> buff = new List<int>();

buff = Route[i].ToList();

buff.Reverse();

for (int j = 1; j < buff.Count; j++)

{

sum += R[buff[j - 1], buff[j]];

}

for (int j = buff.Count - 1; j >= 0; j--)

if (j != Route[i].Count - 1)

str += " -> " + (Route[i][j] + 1).ToString();

else

str += (Route[i][j] + 1).ToString();

str += " = " + sum + "\n";

richTextBoxOut.Text += str;

}

}

// проверка отметки CheckBox 1 (начальных точек)

bool fValidate()

{

if (NodeA1.Checked == true)

ANode[0] = true;

else

ANode[0] = false;

if (NodeA2.Checked == true)

ANode[1] = true;

else

ANode[1] = false;

if (NodeA3.Checked == true)

ANode[2] = true;

else

ANode[2] = false;

if (NodeA4.Checked == true)

ANode[3] = true;

else

ANode[3] = false;

if (NodeA5.Checked == true)

ANode[4] = true;

else

ANode[4] = false;

if (NodeA6.Checked == true)

ANode[5] = true;

else

ANode[5] = false;

// проверка отметки CheckBox 2 (конечных точек)

if (NodeB1.Checked == true)

BNode[0] = true;

else

BNode[0] = false;

if (NodeB2.Checked == true)

BNode[1] = true;

else

BNode[1] = false;

if (NodeB3.Checked == true)

BNode[2] = true;

else

BNode[2] = false;

if (NodeB4.Checked == true)

BNode[3] = true;

else

BNode[3] = false;

if (NodeB5.Checked == true)

BNode[4] = true;

else

BNode[4] = false;

if (NodeB6.Checked == true)

BNode[5] = true;

else

BNode[5] = false;

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

if (ANode[i] == true && BNode[i] == true) // запрет пути с точки в саму себя

return false;

return true;

}

private void button1_Click(object sender, EventArgs e)

{

richTextBoxOut.Text = "";

}

}

}

Размещено на Allbest.ru

...