Автор: Пользователь скрыл имя, 18 Декабря 2011 в 18:50, курсовая работа
Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается. ьььььНахождение кратчайшего пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet.
Введение…………………………………………………………………..………..….3
Глава1. Теоретическая часть…………………………………………..………..……4
1.1 Постановка задачи……………………………………………..…………....4
1.2 Алгоритм Дейкстры………………………………………….……………...4
1.3 Алгоритм решения задачи…………………………..……………………….5
Глава 2. Программный код………………….………………………………………..11
Глава 3. Описание работы программы………………………………………………14
Заключение…………………………………...……………………………………….17
Используемая литература……………………………………………………...……..18
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с.
Информация о работе Разработать программу реализации алгоритма Дейкстры