Автор работы: Пользователь скрыл имя, 24 Декабря 2013 в 11:26, курсовая работа
Данная курсовая работа будет содержать в себе разработку студентом собственного алгоритма нахождения кратчайшего пути между вершинами графа. Алгоритм будет написан в среде быстрой разработке приложений Borland Developed Studio на языке программирования производного от Object Pascal, реализованного в среде разработки Delphi. В начале проекта дадим определения основным понятиям. На примере своего алгоритма наглядно продемонстрируем работу в данной среде, продемонстрировав код алгоритма, представленного в листинге. А также наглядно продемонстрируем, словесно пошагово описывая, выполнение данного проекта.
ВВЕДЕНИЕ 3
1 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И СООТВЕТСТВИЯ 5
1.1 Теория графов как математическия аппарат для решения задач 5
1.2 Алгоритм нахождения кратчайшего пути между двумя точками 9
2 РАЗРАБОТКА И АПРОБАЦИИ АЛГОРИТМА 12
2.1 Составление блок-схемы 12
2.2 Апробация работы алгоритма 15
ЗАКЛЮЧЕНИЕ 21
СПИСКА ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 22
ПРИЛОЖЕНИЕ А
Процедура алгоритма нахождения кратчайшего пути, реализованного в среде разработки Delphi:
unit Unit15;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ComCtrls, Grids;
type
TForm15 = class(TForm)
Button1: TButton;
ListBox1: TListBox;
StringGrid1: TStringGrid;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Edit1: TEdit;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form15: TForm15;
implementation
{$R *.dfm}
const
n = 10; //Количество вершин
//начальные значения
procedure TForm15.FormCreate(Sender: TObject);
var i, j: integer;
begin
Randomize;
for i := 0 to n - 1 do StringGrid1.Cells[i, i] := '0';
for i := 0 to n - 1 do
for j := i + 1 to n - 1 do
begin
StringGrid1.Cells[i, j] := IntToStr(Random(10));
if StringGrid1.Cells[i, j] = '0' then StringGrid1.Cells[i, j] := '-1';
StringGrid1.Cells[j, i] := StringGrid1.Cells[i, j]
end;
end;
procedure TForm15.Button1Click(Sender: TObject);
var
a:array[1..n,1..n] of longint;//матрица смежности (-1 нет ребра)
b:array[1..n]of boolean;//список просмотренных вершин
d:array[1..n] of longint;//расстояния
q, i, j, m, v: integer;
begin
//Ввод данных
q := StrToIntDef(Edit1.Text, 1); //начальная вершина
if (q < 1) or (q > n) then q := 1;
for i := 1 to n do
for j := 1 to n do
a[j, i] := StrToIntDef(StringGrid1.Cells[
//Расчет
fillchar(b,sizeof(b),0);
fillchar(d,sizeof(d), 10000); //бесконечность
d[q] := 0;//расстояние до начальной вершины
for i:=1 to n do
begin
m:=1000;
for j:=1 to n do
if ( (d[j] <= m) and (not b[j]) ) then
begin
m:=d[j];
v:=j;
end;
b[v] := true;
for j:=1 to n do
if ((a[v,j]<>-1)and(not b[j])and (d[v]+a[v,j]<d[j])) then
d[j]:=d[v]+a[v,j];
end;
//Вывод результата
ListBox1.Clear;
for i := 1 to n do
ListBox1.Items.Append(
end;
end.
Граф задается матрицей смежности. Если вершины графа не имеют общей дуги, то соответствующая ячейка матрицы смежности имеет значение -1. Имеется возможность задать начальную вершину графа, от которой будет происходить расчет путей минимальной длины до всех остальных вершин графа. Результат выводится в следующем виде:
n1 –> n2: M,
где n1 – номер начальной вершины;
n2 – номер конечной вершины;
M – минимальный путь между ними.