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

Курсовой проект

по курсу "Логика и основы алгоритмизации в инженерных задачах"

на тему "Алгоритм Флойда"

Выполнил: Белов В.А.

Принял: Пащенко Д.В.



Содержание

• Введение
• 1. Постановка задачи
• 2. Теоретическая часть задания
• 3. Описание алгоритма поставленной задачи
• 4. Пример ручного расчёта задачи и вычислений
• 5. Описание программы
• 6. Тесты
• Заключение
• Список литературы
• Приложение А. Листинг программы
• Приложение B. Результаты работы программы


Введение

В данной курсовой работе необходимо составить программу нахождения кратчайшего расстояния между всеми вершинами взвешенного ориентированного графа. Сам алгоритм нахождения представлен единовременно двумя ученными и несет название "Алгоритм Флойда-Уоршелла". Алгоритм был представлен в 1956 году. В основном Алгоритм Флойда-Уоршелла является эффективным для расчёта всех кратчайших путей в плотных графах, когда имеет место большое количество пар рёбер между парами вершин. Данный программный продукт позволяет автоматизировать расчёт нахождения кратчайшего расстояния между всеми вершинами взвешенного ориентированного графа и призван упростить работу инженерам.



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

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

Для удовлетворения требований задачи я выбрал язык C++. C++ широко используется для разработки программного обеспечения, являясь одним из самых популярных языков программирования. Область его применения очень широка. C++ оказал огромное влияние на другие языки программирования, в первую очередь на Java и C#. Синтаксис C++ унаследован от языка C. Также С++ является объектно-ориентированным языком программирования (ООП). Объектно-ориентированное программирование - это методология программирования, основанная на представлении программ в виде совокупности объектов, каждый из которых является экземпляром определённого класса, а классы образуют иерархию наследования.

С++ доступен для большинства операционных систем, включая Linux, многие модификации Unix, Microsoft Windows, Mac OS X, RISC OS, и многих других.

Преимущества С++:

· Большая безопасность

· Возможность писать обобщенный код с помощью шаблонов

· Возможность использовать объектно-ориентированный подход

· Управление ресурсами с помощью RAII

· Упрощение кода за счет перегрузки функций и операторов

· Более простая обработка ошибок за счет исключений



2. Теоретическая часть задания

Методы маршрутизации. Различают три вида маршрутизации - простую, фиксированную и адаптивную. Принципиальная разница между ними - в степени учета изменения топологии и нагрузки сети при решении задачи выбора маршрута.

Сеть с коммутацией пакетов (или сеть ретрансляции кадров, или сеть АТМ) можно рассматривать как ориентированный граф, в котором каждая вершина соответствует узлу коммутации пакетов, а линиям связи между узлами соответствует пара параллельных ребер, по каждому из которых данные передаются в одном направлении. В такой сети для передачи пакета от узла-источника узлу-получателю по разным линиям через несколько коммутаторов пакетов требуется принять решение о выборе маршрута. Эта задача эквивалентна поиску пути в графе.

Для объединенной сети, такой как Интернет или интранет, представление ее в виде ориентированного графа также является приемлемым. В этом случае каждой вершине соответствует маршрутизатор. Если два маршрутизатора напрямую присоединены к одной и той же локальной или глобальной сети, тогда это двустороннее соединение соответствует паре параллельных ребер, соединяющих соответствующие вершины. Если к сети напрямую присоединены более двух маршрутизаторов, тогда эта сеть представляется в виде множества пар параллельных ребер, каждая из которых соединяет два маршрутизатора. В объединенной сети для передачи IP-дейтаграммы от маршрутизатора-источника к маршрутизатору-приемнику по разным линиям через разные сети и маршрутизаторы пакетов, требуется принять решение о выборе маршрута. Эта задача также эквивалентна поиску пути в графе.

Практически во всех сетях с коммутацией пакетов и во всех объединенных сетях решение о выборе маршрута принимается на основе одной из разновидностей критерия минимальной стоимости. Если выбирается маршрут с минимальным количеством ретрансляционных участков (хопов), тогда каждому ребру, соответствующему ретрансляционному участку, назначается единичный вес. Эта задача соответствует поиску кратчайшего пути в обычном (не взвешенном) графе. Но чаще всего каждому ретрансляционному участку в соответствие ставится определенная величина, называемая стоимостью (cost) передачи. Эта величина может быть обратно пропорциональной пропускной способности линии, прямо пропорциональной текущей нагрузке на эту линию или представлять собой некую комбинацию подобных параметров. При расчете стоимости могут учитываться также такие критерии, как финансовая стоимость использования ретрансляционного участка.

Пусть имеется сеть, состоящая из узлов, соединенных двунаправленными линиями связи, и каждой линии поставлена в соответствие стоимость пересылки данных в каждом направлении. Стоимость пути между двумя узлами определяется как сумма стоимость всех линий, входящих в данный путь. Задача состоит в том, чтобы найти путь с наименьшей стоимостью для каждой пары узлов.

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

Большинство алгоритмов поиска маршрута с наименьшей стоимостью, применяются в сетях с коммутацией пакетов и объединенных сетях, представляют собой вариации одного из двух общих алгоритмов, известных как алгоритм Дейкстры и алгоритм Флойда.



3. Описание алгоритма поставленной задачи

Нам даны матрица весов С(D) орграфа D. Нужно найти расстояния между всеми парами вершин D[i,j] = d(vi,vj).

1. Для всех i = 1,…,n, j = 1,…,n положим D[i,j] = cij .

2. Для всех i = 1,…,n положим D[i,i] = 0.

3. Положим m = 1.

4. Положим i = 1.

5. Положим j = 1.

6. D[i,j] = min (D[i,j], D[i,m] + D[m,j]).

7. Если j < n, то положим j = j + 1 и переходим к шагу 6.

8. Если i < n, то положим i = i + 1 и переходим к шагу 5.

9. Если m < n, то положим m = m + 1 и перейдем к шагу 4, иначе алгоритм заканчивает работу. Полученные значения D[i,j] дают расстояния между вершинами vi и vj.

4. Пример ручного расчёта задачи и вычислений

Определим длины минимальных путей между любыми парами вершин орграфа, изображенного на рис.1-5. Все вычисления будем проводить с помощью матриц D.

Рисунок 1 - Орграф D



Рисунок 2 - Случай 1 и 2

Положим m = 1. Если i = 1 или j = 1, то элементы матрицы остаются без изменения, т.к.

D[i,j] = min (D[i,j], D[i,m] + D[m,j]).

Поэтому рассмотрим случай, когда i = 2, а j = 3. Тогда D[2,3] = min (D[2,3], D[2,1] + D[1,3]) = min (,+5) = .

Далее, j = 4, т.е. D[2,4] = min(D[2,4], D[2,1] + D[1,4]) = min (,+5) = .

Продолжаем процесс до тех пор, пока i 6 и j 6. Положим m = 2 и продолжим рассуждения дальше.

Рисунок 3 - Случай 3 и 4



Рисунок 4 - Случай 5 и 6

Рисунок 5 - Конечный результат вычисления

5. Описание программы

После запуска приложение на экран выводится форма, которая содержит:

1. кнопку, вызывающую функцию генерации исходного графа;

2. поле, в котором для каждого ребра обозначены его вершины;

3. поле, в котором для каждого ребра указан его вес;

4. область отображения исходного графа;

5. поле, в котором отображается матрица кратчайшего расстояния.

В программе реализовано несколько функций:

· void fastcall Refresh (void) - выполняется по нажатию кнопки,

· приводит к немедленной перерисовке изображения на экране в соответствии с новыми случайными значениями матрицы смежности.

· void DrawLine (РепЛ pen, PointF ptl, PointF pt2) - проводит линию, соединяющую две структуры PointF.

· Void DrawString (StringA s, FontA font, BrushA brush, PointF point) - создает заданную текстовую строку в указанном месте с помощью заданных объектов Brush и Font.

6. Тесты

граф алгоритм топология маршрут

В качестве среды разработки была выбрана программа Microsoft Visual Studio 2010, которая содержит в себе все необходимые средства для разработки и отладки модулей и программ. Для отладки программы использовались различные инструменты: точка останова, пошаговое выполнение кода программы, анализ содержимого глобальных и локальных переменных, результаты работы некоторых функций.

Тестирование проводилось в рабочем порядке, в процессе разработки и после завершения написания программы. В процессе тестирования было выявлено и исправлено несколько ошибок.

Для тестирования используем 2 различных по типам наборов данных:

§ Цифры;

§ Любые другие символы кроме цифр;

Результаты тестирования представлены на рисунках 6-7.



Рисунок 6 - Результат тестирования программы с тестируемым набором "цифры"



Рисунок 7 - Результат тестирования программы с тестовым набором "Любые символы"



Заключение

В ходе работы был реализован алгоритм для нахождения матрицы кратчайшего расстояния. Для решения поставленной задачи был выбран алгоритм Флойда - Уоршелла. Были использованы возможности языка программирования C++ и фреймворка Windows forms, базированного на Visual studio 10. Были применены многие методы и особенности языковой структуры си++. Поставленная задача была полностью реализована.



Список литературы

1. Электронный ресурс: https://msdn.microsoft.com Дата обращения: 05.11.2017.

2. Электронный ресурс: https://ru.wikipedia.org/wiki/ Дата обращения: 05.11.2017.

3. Электронный ресурс: http://www.cyberforum.ru/ Дата обращения: 05.11.2017.

4. Дискретная математика для программистов, Р. Хаггарти ISBN 5-94836-016-4, 0-201-73047-2, 2005.

5. Discrete Mathematics with Combinatorics, Джеймс Андерсон - 2-е изд., 2004. - ISBN 978-5-9775-0445-4.



Приложение А. Листинг программы

Файл "Main.cpp"

#include "stdafx.h"

#include "Form1.h"

using namespace forms_kursach;

[STAThreadAttribute]

int main(array<System::String ^> ^args)

{

// Enabling Windows XP visual effects before any controls are created

Application::EnableVisualStyles();

Application::SetCompatibleTextRenderingDefault(false);

// Create the main window and run it

Application::Run(gcnew Form1());

return 0;

}

Файл "Form1.h"

#pragma once

#include <memory.h>

#include <string.h>

#include <stdlib.h>

#include <ctime>

#include <math.h>

#define M_PI 3.14

bool flag = false;

namespace forms_kursach {

using namespace System;

using namespace System::ComponentModel;

using namespace System::Collections;

using namespace System::Windows::Forms;

using namespace System::Data;

using namespace System::Drawing;

/// <summary>

/// Summary for Form1

/// </summary>

public ref class Form1 : public System::Windows::Forms::Form

{

public:

Form1(void)

{

InitializeComponent();

//

//TODO: Add the constructor code here

//

}

protected:

/// <summary>

/// Clean up any resources being used.

/// </summary>

~Form1()

{

if (components)

{

delete components;

}

}

private: System::Windows::Forms::Button^ button1;

private: System::Windows::Forms::Label^ label1;

private: System::Windows::Forms::TextBox^ textBox4;

private: System::Windows::Forms::NumericUpDown^ numericUpDown1;

private: System::Windows::Forms::DataGridView^ dataGridView1;

private: System::Windows::Forms::Label^ label7;

private: System::Windows::Forms::Button^ button2;

private: System::Windows::Forms::RadioButton^ radioButton1;

private: System::Windows::Forms::RadioButton^ radioButton2;

private: System::Windows::Forms::PictureBox^ pictureBox1;

private: System::Windows::Forms::TextBox^ textBox1;

private: System::Windows::Forms::Label^ label2;

private: System::Windows::Forms::Label^ label3;

protected:

private:

/// <summary>

/// Required designer variable.

/// </summary>

System::ComponentModel::Container ^components;

#pragma region Windows Form Designer generated code

/// <summary>

/// Required method for Designer support - do not modify

/// the contents of this method with the code editor.

/// </summary>

void InitializeComponent(void)

{

this->button1 = (gcnew System::Windows::Forms::Button());

this->label1 = (gcnew System::Windows::Forms::Label());

this->textBox4 = (gcnew System::Windows::Forms::TextBox());

this->numericUpDown1 = (gcnew System::Windows::Forms::NumericUpDown());

this->dataGridView1 = (gcnew System::Windows::Forms::DataGridView());

this->label7 = (gcnew System::Windows::Forms::Label());

this->button2 = (gcnew System::Windows::Forms::Button());

this->radioButton1 = (gcnew System::Windows::Forms::RadioButton());

this->radioButton2 = (gcnew System::Windows::Forms::RadioButton());

this->pictureBox1 = (gcnew System::Windows::Forms::PictureBox());

this->textBox1 = (gcnew System::Windows::Forms::TextBox());

this->label2 = (gcnew System::Windows::Forms::Label());

this->label3 = (gcnew System::Windows::Forms::Label());

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown1))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView1))->BeginInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->pictureBox1))->BeginInit();

this->SuspendLayout();

//

// button1

//

this->button1->BackgroundImageLayout = System::Windows::Forms::ImageLayout::None;

this->button1->Enabled = false;

this->button1->Location = System::Drawing::Point(424, 317);

this->button1->Name = L"button1";

this->button1->Size = System::Drawing::Size(118, 34);

this->button1->TabIndex = 0;

this->button1->Text = L"Rezet value";

this->button1->UseVisualStyleBackColor = true;

this->button1->Click += gcnew System::EventHandler(this, &Form1::button1_Click);

//

// label1

//

this->label1->AutoSize = true;

this->label1->BackColor = System::Drawing::SystemColors::Menu;

this->label1->Font = (gcnew System::Drawing::Font(L"Times New Roman", 12, System::Drawing::FontStyle::Regular, System::Drawing::GraphicsUnit::Point,

static_cast<System::Byte>(0)));

this->label1->Location = System::Drawing::Point(588, 12);

this->label1->Name = L"label1";

this->label1->Size = System::Drawing::Size(0, 19);

this->label1->TabIndex = 4;

this->label1->Click += gcnew System::EventHandler(this, &Form1::label1_Click);

//

// textBox4

//

this->textBox4->AccessibleRole = System::Windows::Forms::AccessibleRole::None;

this->textBox4->BackColor = System::Drawing::SystemColors::ScrollBar;

this->textBox4->BorderStyle = System::Windows::Forms::BorderStyle::None;

this->textBox4->Cursor = System::Windows::Forms::Cursors::Arrow;

this->textBox4->Location = System::Drawing::Point(890, 325);

this->textBox4->Name = L"textBox4";

this->textBox4->ReadOnly = true;

this->textBox4->Size = System::Drawing::Size(72, 13);

this->textBox4->TabIndex = 10;

//

// numericUpDown1

//

this->numericUpDown1->Location = System::Drawing::Point(253, 326);

this->numericUpDown1->Maximum = System::Decimal(gcnew cli::array< System::Int32 >(4) {15, 0, 0, 0});

this->numericUpDown1->Minimum = System::Decimal(gcnew cli::array< System::Int32 >(4) {1, 0, 0, 0});

this->numericUpDown1->Name = L"numericUpDown1";

this->numericUpDown1->Size = System::Drawing::Size(39, 20);

this->numericUpDown1->TabIndex = 12;

this->numericUpDown1->Value = System::Decimal(gcnew cli::array< System::Int32 >(4) {1, 0, 0, 0});

this->numericUpDown1->ValueChanged += gcnew System::EventHandler(this, &Form1::numericUpDown1_ValueChanged);

//

// dataGridView1

//

this->dataGridView1->AllowUserToAddRows = false;

this->dataGridView1->AllowUserToDeleteRows = false;

this->dataGridView1->AllowUserToResizeColumns = false;

this->dataGridView1->AllowUserToResizeRows = false;

this->dataGridView1->ColumnHeadersHeightSizeMode = System::Windows::Forms::DataGridViewColumnHeadersHeightSizeMode::AutoSize;

this->dataGridView1->Location = System::Drawing::Point(281, 375);

this->dataGridView1->Name = L"dataGridView1";

this->dataGridView1->Size = System::Drawing::Size(261, 191);

this->dataGridView1->TabIndex = 13;

//

// label7

//

this->label7->AutoSize = true;

this->label7->BackColor = System::Drawing::Color::Transparent;

this->label7->Font = (gcnew System::Drawing::Font(L"Times New Roman", 12, System::Drawing::FontStyle::Bold, System::Drawing::GraphicsUnit::Point,

static_cast<System::Byte>(204)));

this->label7->ForeColor = System::Drawing::Color::Black;

this->label7->Location = System::Drawing::Point(155, 324);

this->label7->Name = L"label7";

this->label7->Size = System::Drawing::Size(92, 19);

this->label7->TabIndex = 14;

this->label7->Text = L"*Матрица:";

//

// button2

//

this->button2->BackgroundImageLayout = System::Windows::Forms::ImageLayout::None;

this->button2->Location = System::Drawing::Point(300, 317);

this->button2->Name = L"button2";

this->button2->Size = System::Drawing::Size(118, 34);

this->button2->TabIndex = 15;

this->button2->Text = L"Calculate";

this->button2->UseVisualStyleBackColor = true;

this->button2->Click += gcnew System::EventHandler(this, &Form1::button2_Click);

//

// radioButton1

//

this->radioButton1->AutoSize = true;

this->radioButton1->Location = System::Drawing::Point(12, 324);

this->radioButton1->Name = L"radioButton1";

this->radioButton1->Size = System::Drawing::Size(67, 17);

this->radioButton1->TabIndex = 17;

this->radioButton1->Text = L"Вручную";

this->radioButton1->UseVisualStyleBackColor = true;

this->radioButton1->CheckedChanged += gcnew System::EventHandler(this, &Form1::radioButton1_CheckedChanged);

//

// radioButton2

//

this->radioButton2->AutoSize = true;

this->radioButton2->Location = System::Drawing::Point(85, 324);

this->radioButton2->Name = L"radioButton2";

this->radioButton2->Size = System::Drawing::Size(64, 17);

this->radioButton2->TabIndex = 18;

this->radioButton2->Text = L"Рандом";

this->radioButton2->UseVisualStyleBackColor = true;

this->radioButton2->CheckedChanged += gcnew System::EventHandler(this, &Form1::radioButton2_CheckedChanged);

//

// pictureBox1

//

this->pictureBox1->BackColor = System::Drawing::SystemColors::HighlightText;

this->pictureBox1->Cursor = System::Windows::Forms::Cursors::WaitCursor;

this->pictureBox1->Location = System::Drawing::Point(12, 12);

this->pictureBox1->Name = L"pictureBox1";

this->pictureBox1->Size = System::Drawing::Size(530, 295);

this->pictureBox1->TabIndex = 19;

this->pictureBox1->TabStop = false;

this->pictureBox1->Click += gcnew System::EventHandler(this, &Form1::pictureBox1_Click_1);

//

// textBox1

//

this->textBox1->Font = (gcnew System::Drawing::Font(L"Times New Roman", 15.75F, System::Drawing::FontStyle::Italic, System::Drawing::GraphicsUnit::Point,

static_cast<System::Byte>(204)));

this->textBox1->Location = System::Drawing::Point(12, 375);

this->textBox1->Multiline = true;

this->textBox1->Name = L"textBox1";

this->textBox1->ReadOnly = true;

this->textBox1->Size = System::Drawing::Size(261, 191);

this->textBox1->TabIndex = 20;

//

// label2

//

this->label2->AutoSize = true;

this->label2->Font = (gcnew System::Drawing::Font(L"Microsoft Sans Serif", 9, System::Drawing::FontStyle::Regular, System::Drawing::GraphicsUnit::Point,

static_cast<System::Byte>(204)));

this->label2->Location = System::Drawing::Point(358, 357);

this->label2->Name = L"label2";

this->label2->Size = System::Drawing::Size(109, 15);

this->label2->TabIndex = 21;

this->label2->Text = L"МАТРИЦА ВЕСОВ";

//

// label3

//

this->label3->AutoSize = true;

this->label3->Font = (gcnew System::Drawing::Font(L"Microsoft Sans Serif", 9, System::Drawing::FontStyle::Regular, System::Drawing::GraphicsUnit::Point,

static_cast<System::Byte>(204)));

this->label3->Location = System::Drawing::Point(21, 357);

this->label3->Name = L"label3";

this->label3->Size = System::Drawing::Size(243, 15);

this->label3->TabIndex = 22;

this->label3->Text = L"МАТРИЦА КРАТЧАЙШЕГО РАССТОЯНИЯ";

//

// Form1

//

this->AccessibleRole = System::Windows::Forms::AccessibleRole::None;

this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::None;

this->BackColor = System::Drawing::SystemColors::ScrollBar;

this->ClientSize = System::Drawing::Size(554, 578);

this->Controls->Add(this->label3);

this->Controls->Add(this->label2);

this->Controls->Add(this->textBox1);

this->Controls->Add(this->pictureBox1);

this->Controls->Add(this->radioButton2);

this->Controls->Add(this->radioButton1);

this->Controls->Add(this->button2);

this->Controls->Add(this->label7);

this->Controls->Add(this->dataGridView1);

this->Controls->Add(this->numericUpDown1);

this->Controls->Add(this->textBox4);

this->Controls->Add(this->label1);

this->Controls->Add(this->button1);

this->FormBorderStyle = System::Windows::Forms::FormBorderStyle::Fixed3D;

this->Name = L"Form1";

this->SizeGripStyle = System::Windows::Forms::SizeGripStyle::Hide;

this->Text = L"Алгоритм Флойда belka58 @inc.";

this->Load += gcnew System::EventHandler(this, &Form1::Form1_Load);

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->numericUpDown1))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->dataGridView1))->EndInit();

(cli::safe_cast<System::ComponentModel::ISupportInitialize^ >(this->pictureBox1))->EndInit();

this->ResumeLayout(false);

this->PerformLayout();

}

#pragma endregion

//====================================================//

// Создаём функцию генерации случайной матрицы

//====================================================//

private: void random(int size, int **mass) {

srand(time(NULL));

for (int i=0; i < size; i++) {

for (int j=0; j < size; j++) {

if(i!=j) mass[i][j] = mass[j][i]=rand()%89+10;

}

}

}

//====================================================//

// Создаём функцию вывода нашей матрицы

//====================================================//

private: void show(int size, int **mass) {

for (int i=0; i < size; i++) {

for (int j=0; j < size; j++) {

//вывод номеров столбцов

dataGridView1->Columns[j]->HeaderCell->Value = Convert::ToString(Convert::ToChar('a' + j));

//вывод номеров строк

dataGridView1->Rows[i]->HeaderCell->Value = Convert::ToString(Convert::ToChar('a' + i));

//вывод значений ячеек

dataGridView1->Rows[i]->Cells[j]->Value = mass[i][j];

}

}

}

//====================================================//

// Функция для ручного ввода чисел в матрицу

//====================================================//

private: void typing(int size, int **mass) {

for (int i = 0; i<size; i++) {

for (int j = 0; j<size; j++) {

//получаем значения из ячеек таблицы

mass[i][j] = Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value);

}

}

}

//====================================================//

// Функция очистки таблицы

//====================================================//

private: void clear() {

for (int i = 0; i<dataGridView1->Rows->Count; i++) {

for (int j = 0; j<dataGridView1->Rows->Count; j++) {

dataGridView1->Rows[i]->Cells[j]->Value = 0;

}

}

dataGridView1->Columns[dataGridView1->Columns->Count-1]->HeaderCell->Value = Convert::ToString(0);

dataGridView1->Rows[dataGridView1->Rows->Count-1]->HeaderCell->Value = Convert::ToString(0);

textBox1->Text = System::Convert::ToString("");

numericUpDown1->Text = System::Convert::ToString(1);

button1->Enabled = false;

}

//====================================================//

// главная функция

//====================================================//

private: void mainfunc(int size, int **mass) {

int n = 0;//размерность матрицы

int **dist = new int*[size];

for (int i = 0; i<size; i++) {

dist[i] = new int[size];//сама матрица весов графа

}

for (int i = 0; i<size; i++) {

for (int j = 0; j<size; j++) {

dist[i][j] = 0;

dist[i][j] = mass[i][j]; //dist - матрица весов графа

}

}

Graphics^ g = this->pictureBox1->CreateGraphics();

n = size;//кол-во вершин

int **coord = new int*[size];

for (int i = 0; i<size; i++) {

coord[i] = new int[2];

}

int x = 0, y = x, xx = 0;

int count_x = 0, count_y = 0;

Brush^ Кисть = gcnew SolidBrush(Color::Red);

Brush^ Кисть 2 = gcnew SolidBrush(Color::Blue);

g->TextRenderingHint = System::Drawing::Text::TextRenderingHint::AntiAlias;

int R = 120;//радиус круга прорисовки

int ox = 265;//половина оси х

int oy = 143;//половина очи y

double i = 180;//i - угол

double psi;//угол в радианах

double fi;//угол в радианах

int count = 0;

for (int j=0; j<size; j++) {

if (count%2==0) i /= 2;

psi = (i * M_PI / 180);

fi = R * sin(psi)/cos(psi);

if(j%2==0) {

coord[j][0] = R * cos(fi)+ox;

coord[j][1] = R * sin(fi)+oy;

}

else {

coord[j][0] = R * cos(fi-180)+ox;

coord[j][1] = R * sin(fi-180)+oy;

}

count++;

if (coord[j][1] > 143) g->DrawString(System::Convert::ToString(Convert::ToChar('a' + j)), Font, Кисть, coord[j][0], coord[j][1]+18);

else g->DrawString(System::Convert::ToString(Convert::ToChar('a' + j)), Font, Кисть, coord[j][0], coord[j][1]-18);

}

int label[1][2];

double Angle; //для вычисления угла наклона ребра относительно x

for (int i = 0; i<size; i++) {

for (int j = 0; j<size; j++) {

if (dist[i][j]> 0) {

label[0][0] = (coord[i][0] + coord[j][0])/2;//подпись ребра x

label[0][1] = (coord[i][1] + coord[j][1])/2;//подпись ребра y

Angle=atan2((float)(coord[i][1]-coord[j][1]),(float)(coord[i][0]-coord[j][0]));

g->DrawString(System::Convert::ToString(dist[i][j]), Font, Кисть 2, label[0][0]+2, label[0][1]+1);

g->DrawLine(gcnew Pen(Color::Black), coord[i][0], coord[i][1], coord[j][0], coord[j][1]);

g->DrawLine(gcnew Pen(Color::Black), coord[j][0], coord[j][1], coord[j][0]+20*cos(Angle-(10*M_PI/180)), coord[j][1]+20*sin(Angle-(10*M_PI/180)));

g->DrawLine(gcnew Pen(Color::Black), coord[j][0], coord[j][1], coord[j][0]+20*cos(Angle+(10*M_PI/180)), coord[j][1]+20*sin(Angle+(10*M_PI/180)));

}

g->DrawEllipse(gcnew Pen(Color::Red),coord[i][0],coord[i][1],3,1);

}

}

//Алгоритм Флойда

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

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

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

if ((dist[i][k] * dist[k][j] != 0) && (i != j))

if ((dist[i][k] + dist[k][j] < dist[i][j]) || (dist[i][j] == 0))

dist[i][j] = dist[i][k] + dist[k][j];

}

textBox1->Text += " ";

for (int z=0; z<size; z++)

textBox1->Text += Convert::ToString("|" + Convert::ToChar('a' + z)+"|" + " ");

textBox1->Text += "\r\n";

for (int i=0; i<size; i++) {

textBox1->Text += Convert::ToString("|" + Convert::ToChar('a' + i)+"|" + " ");

for (int j=0; j<size;j++) {

textBox1->Text += Convert::ToString(dist[i][j] + " "); //Вывод резульатата в textBox1->Text

}

textBox1->Text += Convert::ToString("") + "\r\n";

}

for (int i=0; i < size; i++) {

delete [] coord[i];

}

delete [] coord;

flag = true;

}

private: System::Void Form1_Load(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void label1_Click(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void label2_Click(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void label4_Click(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void textBox3_TextChanged(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {

Graphics^ g = this->pictureBox1->CreateGraphics();

g->Clear(Color::White);

clear();

dataGridView1->ColumnCount = 1;

dataGridView1->RowCount = 1;

radioButton1->Checked = false;

radioButton2->Checked = false;

}

private: System::Void pictureBox1_Click(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void numericUpDown1_ValueChanged(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e) {

//====================================================//

// Получаем размерность матрицы

//====================================================//

int size = Convert::ToInt32(numericUpDown1->Value);

//====================================================//

// генерируем динамический массив под матрицу

//====================================================//

int **mass = new int*[size];

for (int i = 0; i<size; i++) {

mass[i] = new int[size];

}

for (int i = 0; i<size; i++) {

for (int j = 0; j<size; j++) {

mass[i][j] = 0;

}

}

//====================================================//

// создаем таблицу под матрицу

//====================================================//

dataGridView1->ColumnCount = size;

dataGridView1->RowCount = size;

//====================================================//

// Выравнимаем ячейки таблицы

//====================================================//

dataGridView1->AutoResizeRowHeadersWidth(DataGridViewRowHeadersWidthSizeMode::AutoSizeToAllHeaders);

dataGridView1->AutoResizeColumns();

if(radioButton2->Checked) {

random(size, mass);

mainfunc(size, mass);

flag = true;

}

if(radioButton1->Checked) {

typing(size, mass);

mainfunc(size, mass);

flag = true;

}

button1->Visible = true;

if(flag == true) button1->Enabled = true;

show(size, mass);

//====================================================//

// удаляем из памяти массив с матрицей

//====================================================//

for (int i=0; i < size; i++) {

delete [] mass[i];

}

delete [] mass;

}

private: System::Void button3_Click(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void radioButton1_CheckedChanged(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void radioButton2_CheckedChanged(System::Object^ sender, System::EventArgs^ e) {

}

private: System::Void pictureBox1_Click_1(System::Object^ sender, System::EventArgs^ e) {

}

};

}



Приложение B. Результаты работы программы

На рисунках 8 - 10 представлена работа программы в 3 фазах: запуск, ввод данных и вывод результата.

Рисунок 8 - Состояние программы при запуске



Рисунок 9 - Состояние программы при вводе данных



Рисунок 10 - Состояние программы после её выполнения

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

...