Программа определения кратчайшего пути в графе

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

Язык программирования может использовать специальные конструкции для определения и манипулирования структурами данных и управлениями процессом вычислений [5].

Pascal является одним из языков программирования общего назначения.

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

К немало значимым достоинствам языка программирования Pascal можно отнести:

 Простой синтаксис языка. Небольшое число базовых понятий. Программы на Pascal достаточно легко читаемы.

 Достаточно низкие аппаратные и системные требования как самого компилятора, так и программ, написанных на Pascal.

 Универсальность языка. Язык Pascal применим для решения практически всех задач программирования.

 Поддержка структурного программирования, программирования "сверху-вниз", а также объектно-ориентированного программирования.

Однако, первоначально этот язык имел ряд ограничений, таких как:

                       Невозможность передачи функциям массивов переменной длины.

                       Отсутствие нормальных средств работы с динамической памятью.

                       Ограниченная библиотека ввода-вывода.

                       Отсутствие средств для подключения функций написанных на других языках.

                       Отсутствие средств раздельной компиляции.

Часть 2. Система Pascal ABC.

Система программирования Pascal ABC основана на языке Delphi Pascal и призвана осуществить постепенный переход от простейших программ к модульному, объектно-ориентированному, событийному и компонентному программированию. Это система, которая содержит все основные элементы современных языков программирования: модули, классы, перегрузку операторов, интерфейсы, исключения, обобщенные классы, строку мусора, а также некоторые средства параллельного программирования [6].

Специально для учебных целей в данной системе программирования был создан ряд модулей:

                       Модуль растровой графики GraphABC. Он позволяет легко создавать анимацию без мерцания.

 Модуль Events. Позволяет создавать простейшие событийные программы без использования объектов (события представляют собой обычные процедурные переменные).

                       Модули Timers и Sounds. Позволяют создавать таймеры и звуки, которые также реализованы в процедурном стиле.

                       Модуль контейнерных классов Containers. позволяет работать с основными структурами данных (динамические массивы, стеки, очереди, множества), реализованными в виде классов.

 Модуль векторной графики ABCObjects. предназначен для быстрого изучения основ объектно-ориентированного программирования. Позволяет создавать достаточно сложные игровые и обучающие программы.

                       Модуль визуальных компонентов VCL. Имеется редактор форм и инспектор объектов. Технология восстановления формы по коду программы позволяет обойтись для приложения с главной формой одним файлом.

                       Модули исполнителей Робот и Чертёжник для быстрого обучения основам программирования школьников младших и средних классов. [5]

Глава 3. Программа определения кратчайшего пути в графе.

Часть 1. Реализация метода Шимбелла.

Программа «Определение кратчайшего пути в графе. Метод Шимбелла» разработана в среде Pascal ABC.

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

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

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

В окне «меню» располагаются команды, которые можно проделать с графами:

Рис.3.1. Окно «Меню»

                       «Создать граф». При выборе этой процедуры программа предложит вам выбрать размерность символов от ‘c’ до ‘i’.

Рис.3.2. Сообщение о выборе размерности символов.

Предположим, что пользователь выбрал размерность “e”. После корректного ввода размерности создаст пустой граф.

Рис.3.3. Матрица смежности.

Граф нужно заполнить, воспользовавшись диалоговым окном.

Рис.3.4. Диалоговое окно.

                       «Открыть граф». Открывает граф, который введен в самой программе. «Открыть граф из документа». Просит ввести название файла, с которым Вы хотели бы работать дальше.

Рис.3.5. Сообщение о вводе названия файла для работы.

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

Рис.3.6. Окно расширенного «Меню».

                       «Изменить граф». Позволяет ввести некоторые коррективы в уже имеющийся граф.

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

                       «Сохранить граф». Предназначено для сохранения графа в файл.

Рис.3.7. Сообщение о вводе названия файла для сохранения.

                       «Метод Шимбелла». В диалоговом окне всплывают сообщения о направлении графа, а именно из какой и в какую вершину двигаться, и за какое количество ребер. Предположим, что пользователь захотел узнать кратчайший путь из вершины “a” в “c” за 3 ребра. При этом изначально матрица смежности выглядит так:

Рис.3.8. Матрица смежности из примера.

Рис.3.9. Сообщение о вводе входных данных.

После того как все входные данные  введены корректно, программа выводит на экран результат: найдет кратчайший и наидлиннейший пути между заданными вершинами.

Рис.3.10. Вывод результата на экран.

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

Рис.3.11. Визуальный вывод графа.

                       «Выход». Завершение программы.

Сам же алгоритм нахождения кратчайшего пути между вершинами графа описан следующим модулем программы [см. приложение 3.1.1.]

Заключение.

В курсовой работе были рассмотрены основные понятия теории графов, области их применения, определение кратчайшего пути методом Шимбелла, реализованное в Pascal ABC.

В ходе работы были выполнены все поставленные ранее задачи:

                  Изучены источники информации о теории графов. Изучены основные понятия теории графов, операции над графами и способы его задания.

                  Рассмотрены возможности метода Шимбелла для нахождения кратчайшего пути в графе. Этот метод позволяет находить минимальные (максимальные) пути между вершинами, состоящие из заданного количества ребер, а так же подсчитывает длину маршрута (пути).

                  Воспользовалась возможностями Pascal как языком программирования для реализации метода Шимбелла.

                  Разработана программу в Pascal ABC, которая находила бы кратчайший путь методом Шимбелла. Программа выводит длину кратчайшего пути в графе.

                  Проанализированы полученные результаты.

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

Библиографический список:

1.                  Г. Г. Асеев, О. М. Абрамов, Д. Э. Ситников. А90. «Дискретная математика». Учебное пособие. Ростов-на-Дону «Феникс», Харьков «Торсинг». 2003.

2.                  А. И. Белоусов, С. Б. Ткачев. «Дискретная математика»

3.                  О. Е. Акимов. «Дискретная математика. Логика, группы, графы». А39. Лаборатория Базовых Знаний. 2001.

4.                  Берж К. «Теория графов и ее применения». Издательство иностранной литературы. Москва. 1962.

5.                  Википедия. Свободная энциклопедия. http://ru.wikipedia.org/wiki/

6.                  Интернет ресурс. http://sunschool.math.rsu.ru/

7.                  В. Н. Бурков, Д. А. Новиков. «Элементы теории графов»

8.                  В. А. Носов. «Комбинаторика и теория графов». 1999.

Приложения.

1.1.1.    Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых

2.3.1. Паскаль был создан Никлаусом Виртом в 1968-69 годах. Он был опубликован в 1970 году Виртом как небольшой и эффективный язык, чтобы способствовать хорошему стилю программирования, использовать структурное программирование и структурированные данные.

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

3.1.1. procedure Shimbella;                        {метод Шимбелла}

var s,z,i,k:char;

    mas:arr;

    min:integer;                        {для минимального пути}

    max:integer;                        {для максимельного пути}

    matr2:array['a'..'i', 'a'..'i'] of integer;

    leave,dest:char;          {куда, откуда}

    kolvo,c:integer;         {кол-во ребер}

function min_mas(mas:arr):integer;      {наикратчайший путь}

begin

   min:=mas['a'];

   for s:='a' to n do

     if (mas[s]<>0) then

        if min=0 then min:=mas[s]

        else  if mas[s]<min then min:=mas[s];

   min_mas:=min;                           {нашли мин.}

end;

function max_mas(mas:arr):integer;         {наидлиннейший путь}

begin                             {аналогичным образом, но}

   max:=mas['a'];                              {немного иначе}

   for s:='a' to n do

     if (mas[s]<>0) then

        if max=0 then max:=mas[s]

        else  if mas[s]>max then max:=mas[s];

   max_mas:=max;

end;

function mnozh(matr,matr2:arr2):arr2;   {для минимального пути}

var i,k,z:char;

    matr3:arr2;

begin

  for i:='a' to n do

      for k:='a' to n do begin

          for z:='a' to n do begin

             mas[z]:=matr[i,z]+matr2[z,k];            {если при сложении получилось тоже число}

             if mas[z]=matr[i,z] then mas[z]:=0;          {(хотя бы одно из них = 0)}

             if mas[z]=matr2[z,k] then mas[z]:=0; {то значение тоже = 0}

             end;

          matr3[i,k]:=min_mas(mas);

      end;

mnozh:=matr3;

end;

function mnozh2(matr,matr2:arr2):arr2;      {для максимал. пути}

var i,k,z:char;

    matr3:arr2;

begin

  for i:='a' to n do

      for k:='a' to n do begin

          for z:='a' to n do begin

             mas[z]:=matr[i,z]+matr2[z,k];         {если при сложении получилось тоже число}

             if mas[z]=matr[i,z] then mas[z]:=0;         {(хотя бы одно из них = 0)}

             if mas[z]=matr2[z,k] then mas[z]:=0;   {то значение тоже = 0}