ПРОГРАММНОЕ СРЕДСТВО РЕАЛИЗАЦИИ АЛГОРИТМА «ФЛОЙ-ДА–УОРШЕЛА». Итог курсового проекта. Программное средство реализации алгоритма флойдауоршела

• Название: Программное средство реализации алгоритма флойдауоршела
• Анкор: ПРОГРАММНОЕ СРЕДСТВО РЕАЛИЗАЦИИ АЛГОРИТМА «ФЛОЙ-ДА–УОРШЕЛА
• Дата: 07.11.2022
• Размер: 1.65 Mb.
• Имя файла: Итог курсового проекта.docx
• Тип: Пояснительная записка; #775652
• страница: 6 из 10

2.3 Разработка алгоритма задачи

Алгоритм – конечная совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи.

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

Разработка алгоритма включает в себя выбор метода проектирования алгоритма, выбор формы записи алгоритма (блок-схемы и др.), выбор тестов и метода тестирования, проектирование самого алгоритма.

Блок-схема – это графическое представление алгоритма, в котором он изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.

Рассмотрим граф с вершинами {v₁, v₂… v_n}. В графе существует путь р_ij от v_i до v_j, который проходит через множество вершин. Обозначим через ­– длину кратчайшего пути из i в j, проходящего через вершины v₁…v_k-1. Расширим множество разрешенных вершин на одну: v₁…v_k. При этом возможны две ситуации. Ситуация 1: вершина v_k не входит в кратчайший путь от i в j. Длина кратчайшего пути не изменится, соответственно . Ситуация 2: вершина v_k входит в кратчайший путь от i в j. Новый кратчайший путь разбит вершиной v_k на два пути р_ik и р_kj (кратчайшее расстояние от v_i до v_k и кратчайшее расстояние от v_k до v_j). Значит общая длина пути . Вершина v_k в данных путях либо конечный, либо начальный элемент, в множество промежуточных она не входит, поэтому . Для обоих рассмотренных случаев минимальный путь складывается из минимальных длин путей для предыдущих значений. Зная начальные значения при k=0 можно последовательно найти все остальные пути. - минимальное расстояние от i до j проходящее через 0 вершин, другими словами это длина прямых соединений между i до j, которое известно с.

При разработке алгоритма решения был использован способ языка графических символов. Алгоритм работы Флойда-Уоршелла проиллюстрирован на блок-схеме (рисунок 2.3).


Рисунок 2.3 – Блок-схема алгоритма Флойда-Уоршелла
На блок-схеме изображен основной алгоритм Флойда­–Уоршелла – нахождение кратчайшего пути в графе.

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

2.4 Интерфейс программы

Интерфейс – это совокупность средств, методов и правил взаимодействия (управления, контроля и т.д.) между элементами системы [10-11].

Под интерфейсом программы обычно понимают самый абстрактный из всех интерфейсов – пользовательский интерфейс.

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

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

В действительности интерфейс пользователя объединяет в себе все элементы и компоненты программы, которые способны оказывать влияние на взаимодействие пользователя с программным обеспечением, это не только экран, который видит пользователь.

В понятие пользовательского интерфейса компьютерной системы входят следующие составляющие:

• 
  графическая среда – изображение на экране;
  
• 
  набор управляющих элементов пользовательского интерфейса и их расположение на экране;
  
• 
  технологии взаимодействия пользователя с системой.
  

Управляющие элементы пользовательского интерфейса – это графические элементы (кнопки, списки, диалоговые окна и т.п.), которые позволяют осуществлять какие-либо действия с компьютерной системой (например, выбирать пункты и свойства объектов).

К пользовательскому интерфейсу приложения должны предъявляться следующие требования:

• 
  функциональность (соответствие задачам пользователя);
  
• 
  понятность и логичность (логичность расположения элементов на форме и удобство при эксплуатации программы);
  
• 
  обеспечение защиты от человеческих ошибок;
  
• 
  интуитивная ясность.
  

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

• 
  основное окно создания графа (рисунок 2.4);
  
• 
  окно настройки цвета вершины (рисунок 2.5).
  

Рисунок 2.4 – Основное окно создание графа

Рисунок 2.5 – Окно настройки цвета вершины
В основном окне по созданию графов заметную часть занимает само поле, в котором располагается граф.

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

Ниже под списком располагаются действия, которые может выполнить пользователь: действие «Кратчайший путь», действие «Удалить ребро», действие «Отчистить от ребер», действие «Отчистить поле». За действиями следует следующая логика:

– действие «Кратчайший путь» – за этим действием следует запуск алгоритма Флойда-Уоршелла по нахождению кратчайшего пути;

– действие «Удалить ребро» – за этим действием следует удаление установленного последнего ребра;

– действие «Отчистить от ребер» – за этим действием следует удаление всех ребер между вершинами;

– действие «Отчистить поле» – за этим действием происходит отчистка главного поля.

Применяя соглашение формы checkbox «Неориентированный» пользователь получает граф у которого все ребра являются неориентированными.

При выделении вершины становятся доступны функции «Удаление» и «Изменения цвета» текущей вершины.

Ниже под полем располагается меню под названием «Toolbox» в этом меню пользователь выбирает работу курсора в поле графа: «Перемещение», «Вершина», «Ребро», «Ластик». Под названием этих функций подразумевается следующие

– функция «Перемещения» – предоставляет возможность свободно располагать граф в поле;

– функция «Вершина» – предоставляет возможность обрисовывать вершины в поле графа;

– функция «Ребро» – предоставляет возможность соединения между двумя вершинами;

– функция «Ластик» – предоставляет возможность стереть любой объект в поле.

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