Разработать программу реализации алгоритма Дейкстры

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

УФИМСКИЙ  ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ  УНИВЕРСИТЕТ

Кафедра вычислительной математики и кибернетики

 
 
 
 
 

           ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

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

 

по дисциплине:

«Дискретная математика»

на тему:

«Разработать программу реализации алгоритма Дейкстры»

 
 
 
 
 
 
 

               Студентка гр. МИЭ-232: А.Р.Исламгалеева

                  Руководитель  курсовой работы: доц. О.Н. Сметанина

Оценка  курсовой работы:__________________

Принял:_______________ Дата _____________

 
 
 

             Уфа 2011

 
 

Содержание

Введение…………………………………………………………………..………..….3

 

Глава1. Теоретическая  часть…………………………………………..………..……4

 

1.1   Постановка задачи……………………………………………..…………....4

 

1.2  Алгоритм Дейкстры………………………………………….……………...4

 

1.3 Алгоритм решения задачи…………………………..……………………….5

 

Глава 2. Программный код………………….………………………………………..11

 

Глава 3. Описание работы программы………………………………………………14

 

Заключение…………………………………...……………………………………….17

 

Используемая  литература……………………………………………………...……..18

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                                                  Введение

     Благодаря своему широкому применению, теория о  нахождении кратчайших путей в последнее  время интенсивно развивается.                                                                                                                          ьььььНахождение  кратчайшего  пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet. Кратчайший путь рассматриваетсяmmприmmпомощиmmнекоторогоmnматематическогоььобъекта,ьназываемогоььграфом.                                                                                                                                               тттттОдин из более эффективных алгоритмов нахождения кратчайшего пути является алгоритм Дейкстры (используется для нахождения оптимального маршрутаььмеждуььвершинами).                                                                                                                                                                          ьььььУказанный алгоритм  легко выполняется при малом количестве вершин в графе. При увеличении их количества задача поиска кратчайшего пути усложняется. Компьютерные средства и информационные технологии повысили возможности такого всеохватывающего метода изучения и создания, как моделирования объектов, явлений и процессов – как тех, что существуют в природе, так и тех, что создаются человеком искусственно                                                             Бббб.Из всех объектно-ориентированных языков программирования Делфи является одним из наиболее широко используемым. И именно с его помощью в данном курсовом проекте реализуется алгоритм Дейкстры.         

 
 
 
 
 
 

             

 
 
 
 
 
 
 
 

Глава1. Теоретическая часть

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

Основной  задачей данного курсового проекта  является программная

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

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

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

 

1.2 Алгоритм Дейкстры

 

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

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

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

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

  1. Рассмотрим все дуги, ведущие из помеченных вершин в одну непомеченную. Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.
  2. Выберем из этих путей кратчайший. А затем выберем среди них самый короткий ко всем непомеченным вершинам, и пометим вершину, к которой он ведет.

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

 
 
 
 
 
 
 
 
 

1.3 Алгоритм решения задачи

 

Каждой  вершине из V сопоставим метку —  минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

 

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

 

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

Пример.

Рассмотрим  выполнение алгоритма на примере  графа, показанного на рисунке. Пусть  требуется найти расстояния от 1-й  вершины до всех остальных.

 

Кружками  обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

 

 

Первый  шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

 

 

Первый  по очереди сосед вершины 1 — вершина 2, потому что длина пути до неё  минимальна. Длина пути в неё через  вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-ой в 2-ую, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

 
 
 

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.

 
 

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

 

 

Второй  шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей  выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

 

Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

 

Следующий сосед вершины 2 — вершина 3, так  как имеет минимальную метку  из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина  такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

 
 

 

 Ещё  один сосед вершины 2 — вершина  4. Если идти в неё через 2-ю,  то длина такого пути будет  равна сумме кратчайшего расстояния  до 2-ой вершины и расстояния  между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22<, устанавливаем метку вершины 4 равной 22.

 
 

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

 

 

Третий  шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

 

 

Дальнейшие  шаги. Повторяем шаг алгоритма  для оставшихся вершин. Это будут  вершины 6, 4 и 5, соответственно порядку.

 

 

 

Завершение  выполнения алгоритма. Алгоритм заканчивает  работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Глава 2. Програмный код

unit Main; ;   // модуль формы

interface

 

uses// стандартные модули

 

  SysUtils, Windows, Messages, Classes, Graphics, Controls,

  Forms, Dialogs, StdCtrls, Buttons, ExtCtrls, Menus, ComCtrls, about, Tabs,

  Grids, Unit1, Unit2;

 

type     // типы  объектов графического интерфейса и процедуры модуля

 

  TMainForm = class(TForm)

    MainMenu: TMainMenu;

    FileNewItem: TMenuItem;

    FileOpenItem: TMenuItem;

    FileSaveItem: TMenuItem;

    FileExitItem: TMenuItem;

    StatusLine: TStatusBar;

    OpenDialog: TOpenDialog;

    SaveDialog: TSaveDialog;

    SpeedBar: TPanel;

    NewBtn: TSpeedButton;

    OpenBtn: TSpeedButton;

    SaveBtn: TSpeedButton;

    AboutBtn: TSpeedButton;

    ExitBtn: TSpeedButton;

    Label1: TLabel;

    TabSet1: TTabSet;

    Notebook1: TNotebook;

    Memo1: TMemo;

    GrafField: TImage;

    Matrix: TStringGrid;

    Label2: TLabel;

    Label3: TLabel;

    Button1: TButton;

    Button2: TButton;

    N1: TMenuItem;

    N2: TMenuItem;

    ClearBtn: TSpeedButton;  { E&xit }

    procedure FormCreate(Sender: TObject);

    procedure ShowHint(Sender: TObject);

    procedure FileNew(Sender: TObject);

    procedure FileOpen(Sender: TObject);

    procedure FileSave(Sender: TObject);

    procedure FileExit(Sender: TObject);

 

    procedure HelpMenuClick(Sender: TObject);

    procedure AboutBtnClick(Sender: TObject);

    procedure Timer1Timer(Sender: TObject);

    procedure TabSet1Change(Sender: TObject; NewTab: Integer;

      var AllowChange: Boolean);

    //

    procedure Clear_aPoints;

    procedure ClearField;

    function GetX(NPoint: byte): byte;

    function GetY(NPoint: byte): byte;

    function GetNumber(x,y: byte): byte;

    procedure DrawPoint(X, Y, pNum: byte;  Color: TColor);

    procedure PutPoint(X, Y: byte);

    procedure Redraw;

    procedure RemovePoint(X, Y: byte);

    procedure PutEdge(First, Second: byte; Color: TColor);

    procedure GrafFieldMouseDown(Sender: TObject; Button: TMouseButton;

      Shift: TShiftState; X, Y: Integer);

    procedure GrafFieldMouseMove(Sender: TObject; Shift: TShiftState; X,

      Y: Integer);

    procedure GrafFieldMouseUp(Sender: TObject; Button: TMouseButton;

      Shift: TShiftState; X, Y: Integer);

    function BinToHex(Bin: String): String;

    function HexToBin(Hex: String): String;

    procedure seachmas(na, nb:integer);

    procedure Button1Click(Sender: TObject);

    procedure Button2Click(Sender: TObject);

    procedure N2Click(Sender: TObject);

    procedure ClearBtnClick(Sender: TObject);

 

  private

    { Private declarations }

  public

    { Public declarations }

  end;

 
 

const

  pOX = 8;  //кол-во точек по оси OX

  pOY = 8;  //кол-во  точек по оси OY

  pD = 30;  //расстояниемежду  2 соседними точками

  pE = 20;  //отступ 1-го ряда точек от края поля

 

var

  MainForm: TMainForm;

  //

  aPoints: array [1..pOX, 1..pOY] of boolean;

  PointCounter: byte;   //Количество вершин графа

  i, j: byte;           //координаты по X и по Y

  Grafrect: TRect;      //Набор координат поля графа

  EdgeColor, PointColor, NumColor, FieldColor, GridColor: TColor;

  Drawing: boolean;     //Включен или выключен режим рисования ребра

  Origin, MovePt: TPoint;  //Точка начала рисования ребра.  Текущая конечная точка ребра

  //переменные  для ParamForm

  isDirection: Boolean;      //Ориентированный граф или нет.

  isWeight: Boolean;     //Взвешенный граф или нет.

  OpenYN: Boolean; //Открыт в настоящее время какой-либо граф или нет.

  //переменные  для AskForm

  sWeight: string;  //вес ребра

  //доп. переменные

  a,b: integer;

  pam:array[1..20] of integer;

  pam1:array[1..20] of boolean;

  k: integer;

  sum,nom,dlin: integer;

 

implementation

uses

  unit3;

procedure TMainForm.FormCreate(Sender: TObject);

begin

  Application.OnHint := ShowHint;

  NoteBook1.PageIndex:=0;  *

*см. приложение 1

 
 
 
 

Глава 3. Описание работы программы

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

 

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

Пример  решения задачи:

Найти длину кратчайшего пути из точки 1 в точку 5

                                                  

  

 

  

 
 
 
 

Заключение

 

     Таким образом, в процессе создания данного  проекта разработана программа, реализующая алгоритм Дейкстры в Borland.Delphi.7.Personal.

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

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Используемая  литература.

1. Н.Кристофидес Терия графов. Алгоритмический подход. -М.: Мир, 1978.-432 с

2. Дискретная математика для программистов/ Ф.А. Новиков. — СПб.: Питер, 2003.—304с.                                                                                                                                            3. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий.м—СПб.:мБХБ-Петербург,м2006.—400с.                                                             

Разработать программу реализации алгоритма Дейкстры