Нахождение кратчайшего пути между городами Минской области

Инструментами разработки будут  являться:

• среда Visual Studio 2008;
• язык программирования C#;
• среда проектирование Rational Rose

Среда разработки Microsoft Visual Studio — это набор инструментов и средств, предназначенных для помощи разработчикам программ любого уровня квалификации в решении сложных задач и создания новаторских решений. Разработчикам программного обеспечения часто приходится решать ряд проблем, чтобы создавать удачные программы. Роль Visual Studio заключается в том, чтобы улучшить процесс разработки и упростить разработку высокоэффективных программ.

Средства Visual Studio позволяют разработчикам работать с большей отдачей и затрачивать меньше усилий на повторяющиеся задачи. Следует отметить высокопроизводительные редакторы кода, поддержку технологии IntelliSense, мастеров и различных языков кодирования в одной интегрированной среде разработки (IDE), а также продукты управления жизненным циклом приложений (ALM) в Microsoft® Visual Studio® Team System. В новых версиях Visual Studio постоянно появляются новые средства, позволяющие разработчикам сосредоточиться на решении основных проблем, а не на рутинной работе.

Разработчики, применяющие  Visual Studio, получают в свое распоряжение интегрированный продукт, включающий инструменты, серверы и службы. Продукты Visual Studio отлично работают вместе — не только один с другим, но и с прочими программами Майкрософт, включая серверные продукты и приложения Microsoft Office.

В Visual Studio содержатся инструменты для всех этапов разработки программного обеспечения (разработка, тестирование, развертывание, интеграция и управления) и для разработчиков любого уровня квалификации, от новичков до опытных специалистов. Visual Studio поддерживает разработку для различных типов устройств — ПК, серверов, сетевых и мобильных устройств.

Visual Studio разрабатывается таким образом, чтобы обеспечить высокую надежность и совместимость. Visual Studio обладает удачным сочетанием безопасности, масштабируемости и взаимодействия. В Visual Studio всегда поддерживаются новейшие технологии, но везде, где это возможно, обеспечивается обратная совместимость.[8]

C# – элегантный, строго  типизированный объектно-ориентированный  язык, предназначенный для разработки  разнообразных безопасных и мощных  приложений, выполняемых в среде  .NET Framework. На языке C# можно разрабатывать обычные клиентские приложения Windows, веб-службы XML, распределенные компоненты, приложения типа «сервер-клиент», приложения баз данных и многие-многие другие. В Visual C# 2008 имеется расширенный редактор кода, конструкторы с удобным пользовательским интерфейсом, встроенный отладчик и многие другие средства, призванные упростить разработку приложений на языке C# версии 3.0 и .NET Framework версии 3.5.

Как объектно-ориентированный  язык, C# поддерживает понятия инкапсуляции, наследования и полиморфизма. Все  переменные и методы, включая метод  Main – точку входа приложения – инкапсулируются в определения классов. Класс может наследовать непосредственно из одного родительного класса, но может реализовывать любое число интерфейсов. Для методов, которые переопределяют виртуальные методы в родительском классе, необходимо ключевое слово override, чтобы исключить случайное повторное определение. В языке C# структура похожа на облегченный класс: это тип, распределяемый по стопкам, реализующий интерфейсы, но не поддерживающий наследование.

В дополнение к основным описанным объектно-ориентированным  принципам, язык C# упрощает разработку компонентов программного обеспечения  благодаря нескольким инновационным  конструкциям языка, в число которых  входят следующие:

• инкапсулированные подписи методов, называемые делегатами, которые поддерживают строго-типизированные уведомления о событиях;
• свойства, выступающие в роли методов доступа для закрытых переменных-членов;
• атрибуты с декларативными метаданными о типах во время выполнения;
• встроенные комментарии XML-документации.[8]

Ни одна из методологий  разработки программ не обходится без  некоторого инструмента.  Разработка крупных программных систем в  современных условиях невозможна без  использования средств автоматизации  разработки программного обеспечения  – CASE-средств (Computer Aided Software Engineering). Наиболее известное CASE-средство, поддерживающее объектно-ориентированный подход анализа и проектирования, – система Rational Rose. Семейство продуктов Rational Rose обеспечивает разработчика полным набором инструментов визуального моделирования, позволяющим получать высоконадежные и эффективные решения, удовлетворяющие требованиям, предъявляемым современным уровнем информационных технологий к готовым программным продуктам, и пригодные для использования в распределенных средах «клиент/сервер» и системах реального времени.

Из  основных возможностей можно перечислить  следующие:

• мощный графический язык моделирования предметной области, обладающий высоким уровнем формализации и поддерживающий объектно-ориентированную методологию.
• удобная навигация между элементами модели при помощи «инспектора» проекта;
• хранение результатов проектирования в виде единой модели;
• поддержка работы над проектом группы разработчиков;
• мощная система подготовки отчетов и документации о проекте;
• возможности синтеза программ практически на всех современных объектно-ориентированных языках;
• поддержка компонентных технологий построения программных систем;
• широкие возможности по проектированию ПО различной архитектуры, от простых программ, до крупных «клиент-серверных» систем и Интернет-приложений;
• возможность реинженеринга модели на основе исходных текстов программы. Этим обеспечивается поддержание единства проектной информации и реализации;
• настройка и расширение функциональных возможностей CASE среды путем установки модулей расширения, в первую очередь для поддержки различных языков программирования.[9]

 

3 Проектирование задачи

3.1 Требования к приложению

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

• оптимизировать маршрут;

• сохранение маршрута в файл с расширением .txt;

• поиск города.

Графический интерфейс должен быть простым, интуитивно понятным и  дружелюбным.

Средства защиты программы  зависят от самого пользователя, он сам выбирает каталог для сохранения файла, и сам, используя возможности операционной системы, устанавливает защиту файла. Данные же самой программы защищать незачем, ибо они не несут и не могут нести никакой материальной ценности.

 

3.2 Концептуальный прототип

Концептуальный прототип состоит из описания внешнего пользовательского  интерфейса, а именно, элементов  управления.

При создании данного приложения важную роль играют формы, так как  они являются основным диалоговым средством  работы пользователя. Разрабатываемое  приложение будет содержать несколько  форм: две основные формы и пять дополнительных. Такая структура  интерфейса позволит классифицировать основные функции программы по группам.

При проектировании концептуального  прототипа были разработаны следующие  формы:

• «Оптимизация маршрута»;
• «О программе».

На форме «Оптимизация маршрута» находится:

• компонент MenuStrip1 для удобства работы;
• компонент SaveFileDialog1 для сохранения в текстовый файл маршрута файл;
• компонент CheckedListBox1 для выбора города отправления;
• компонент CheckedListBox2 для выбора города прибытия;
• компонент CheckedListBox3 для выбора города проезда;
• компоненты Label1, Label2 и Label3 для дополнительной информации;
• компоненты Button1, Button2 и Button3 для выбора пункта назначения, города проезда и отправления соответственно;
• компонент Button6 перехода к выбору города на карте;
• компонент Button5 для нахождения кратчайшего маршрута;
• компонент Button4 для поиска города;
• компонент RadioButton1 для выбора поиска по городам отправления;
• компонент RadioButton2 для выбора поиска по городам прибытия;
• компонент RadioButton3 для выбора поиска по городам проезда;
• компонент TextBox2 для введения данных для поиска;
• компонент Button5 для нахождения кратчайшего пути;
• компонент TextBox1 для вывода кратчайшего маршрута;
• компонент TextBox1 для вывода кратчайшего расстояния.

На форме «О программе» находится:

• компоненты Label1-Label9 для получения информации о программе разработчике, а так же контакты с разработчиком;
• компонент LinkLabel2 и LinkLabel1 для вывода адресов сайтов.
• компонент Button2 для сохранения информации в файл.

На форме «Карта» находится:

• компонент PictureBox1 для вывода изображения карты;
• компоненты CheckBox1 – CheckBox25 для выбора городов;
• компонент СontextMenuStrip1 для подтверждения выбора городов.

 

 

 

 

3.3 Организация данных

Организация данных подразумевает  создание модели данных, главными элементами которой являются сущности и их связи.

В разделе 2.2 на рисунке 1 представлена схема «Сущность-связь», на которой отображены главные сущности задачи: «Место отправления»,  «Пункт назначения», «Пользователь», «Список городов».

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

 

 

3.4 Функции и элементы управления

При нажатии клавиши «Найти кратчайший путь», использую алгоритм поиска кратчайшего пути на графах Флойда, программный продукт определяет кратчайший путь следования и его расстояние, и выводит в соответствующую строку пути и его расстояние. Далее, пожеланию, пользователь может сохранить данные в файл.

Программный код реализации данных функции представлен ниже.

 

class Optimization

    {       

        int[,] D = new int[30, 30]   

                //1

                {{0,9999,9999,9999,9999,9999,9999,9999,9999,9999,41,9999,64,9999,133,9999,9999,9999,65,115,55,9999,9999,9999,9999,9999,38,44,45,26},

                //2

                {9999,0,86,9999,9999,9999,69,9999,9999,79,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,44,9999,9999,9999,9999},

                //3

                {9999,86,0,9999,9999,9999,20,9999,999,46,60,9999,9999,9999,9999,9999,9999,54,9999,9999,9999,9999,9999,9999,9999,9999,45,9999,9999,9999},

                //4

                {9999,9999,99999,0,9999,9999,9999,9999,9999,99999,83,99999,9999,23,9999,9999,9999,92,99999,99999,9999,9999,99999,9999,9999,9999,99999,9999,9999,9999},

                //5

                {9999,9999,9999,9999,0,9999,99999,9999,9999,9999,9999,9999,9999,41,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,999,9999,37,9999},

                //6

                {9999,9999,9999,9999,9999,0,9999,9999,9999,9999,9999,9999,93,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,38,35,9999,9999,9999,9999,16},

                //7

                {9999,69,20,9999,9999,9999,0,9999,9999,9999,41,9999,9999,9999,9999,9999,9999,9999,9999,9999,21,9999,9999,9999,9999,9999,9999,9999,9999,9999},

                //8

                {9999,9999,9999,9999,9999,9999,9999,0,39,9999,9999,9999,9999,9999,9999,9999,20,9999,9999,76,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999},

                //9

                {9999,9999,9999,9999,9999,9999,9999,39,0,9999,9999,9999,9999,9999,9999,9999,34,9999,9999,41,9999,9999,9999,9999,52,9999,9999,9999,9999,9999},

                //10

                {9999,79,46,9999,9999,9999,9999,9999,9999,0,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999},

                //11

                {41,9999,60,83,9999,9999,41,9999,9999,9999,0,9999,9999,9999,115,9999,9999,32,9999,9999,29,9999,9999,9999,9999,9999,9999,9999,9999,9999},

                //12

                {9999,99999,9999,9999,9999,9999,9999,9999,9999,9999,9999,0,9999,9999,9999,9999,9999,9999,9999,49,9999,9999,37,9999,9999,9999,9999,9999,9999,9999},

                //13

                {64,9999,9999,9999,9999,93,9999,9999,9999,9999,9999,9999,0,9999,9999,9999,9999,9999,9,9999,9999,9999,68,9999,9999,32,9999,9999,9999,9999},

                //14

                {9999,9999,9999,23,41,9999,9999,9999,9999,9999,9999,9999,9999,0,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,34,9999,9999},

                //15

                {133,9999,9999,9999,9999,9999,9999,9999,9999,9999,115,9999,9999,9999,0,12,9999,107,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999},

                //16

                {9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,12,0,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999},

                //17

                {9999,9999,9999,9999,9999,9999,9999,20,34,9999,9999,9999,9999,9999,9999,9999,0,9999,9999,75,9999,9999,9999,33,57,9999,9999,9999,9999,9999},

                //18

                {9999,9999,54,9999,9999,9999,9999,9999,9999,9999,32,9999,9999,9999,107,9999,9999,0,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999},

                //19

                {65,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9,9999,9999,9999,9999,9999,0,9999,9999,9999,9999,9999,9999,26,9999,9999,9999,9999},

                //20

                {115,9999,9999,9999,9999,9999,9999,76,41,9999,9999,49,9999,9999,9999,9999,75,9999,9999,0,9999,37,49,9999,75,9999,9999,9999,9999,9999},

                //21

                {55,9999,9999,9999,9999,9999,21,9999,9999,9999,29,9999,9999,9999,9999,9999,9999,9999,9999,9999,0,9999,9999,9999,9999,80,9999,9999,9999,9999},

                //22

                {9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,37,9999,0,9999,9999,9999,9999,9999,9999,9999,9999},

                //23

                {9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,9999,68,9999,9999,9999,9999,9999,9999,49,9999,9999,0,9999,9999,9999,9999,9999,9999,9999},