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

Автор: Пользователь скрыл имя, 18 Декабря 2011 в 18:50, курсовая работа

Описание работы

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается. ьььььНахождение кратчайшего пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet.

Содержание

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

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

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

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

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

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

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

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

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

Работа содержит 1 файл

Пояснительная записка.doc

— 238.50 Кб (Скачать)

    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с.                                                             

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