| DELETE
|
O(log N)
|
O(log N)
|
O(log N)
|
O(log N)
|
O(log N)
|
O(log N)
|
O(log N)
|
O(log N)
|
O(1)
|
{************************************************************}
{ }
{ Алгоритм Дейкстры }
{ Copyright (c) 2008 ТГИМЭУиП }
{ Факультет управления/ 461 группа }
{ }
{ Разработчик: Долганова Анастасия }
{ Модифицирован: май 2008 }
{ }
{************************************************************}
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids, jpeg, ExtCtrls;
const
MAX = 200; // максимальная длина пути между двумя вершинами
CHCOUNT = 6; // количество частей
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Label1: TLabel;
Memo1: TMemo;
Button4: TButton;
Button6: TButton;
ListBox1: TListBox;
Label2: TLabel;
Button1: TButton;
procedure Button4Click(Sender: TObject);
procedure Button6Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
private
// матрица весов (расстояний между частями)
Weights: array [0..CHCOUNT-1, 0..CHCOUNT-1] of integer;
// индекс части- пункта отправления
first: integer;
procedure GetWeightsMatrix;
procedure FirstCountStep;
procedure GoCount;
procedure StraightWay;
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
const CH: array [1..6] of string[3]=
('1-я', '2-я', '3-я',
'4-я', '5-я', '6-я');
procedure TForm1.Button4Click(Sender: TObject); // задает пути между частями случайным образом
var
i, j: integer;
flag: real; // существует ли путь
begin
for i:=1 to StringGrid1.ColCount-1 do
begin
for j:=i+1 to StringGrid1.RowCount-1 do
begin
flag := random;
if (flag>0.5) then
begin
StringGrid1.Cells[i,j] := IntToStr(random(MAX));
StringGrid1.Cells[j,i] := StringGrid1.Cells[i,j];// заполняет таблицу
end;
end;
end;
end;
procedure TForm1.GetWeightsMatrix; // заполняет матрицу весов Weights
var
i, j: integer;
begin
for i:=0 to CHCount-1 do
Weights[i,i] := 0; // из части в саму себя
for i:=0 to CHCount-1 do
for j:=0 to CHCount-1 do
begin
if (StringGrid1.Cells[i + 1, j + 1] <> '') then
Weights[i, j] := StrToInt(StringGrid1.Cells[i + 1, j + 1]);
end;
end;
procedure TForm1.Button6Click(Sender: TObject); вызывает процедуры для расчета
begin
Memo1.Lines.Clear;
GetWeightsMatrix; // перебрасывает пути в матрицу
FirstCountStep; // инициализирует расчет
StraightWay; // находит прямые пути
GoCount; // запускает расчет
end;
procedure TForm1.FirstCountStep; // проверяет, выбрана ли часть из списка
var
i: integer;
begin
first := -1;
for i := 0 to CHCount - 1 do
begin
if ListBox1.Selected[i] then
first := i;
end;
if (first = -1) then
begin
MessageDlg(‘ ошибка: вы не выбрали начальную часть в списке!',
mtError, [mbOK], 0);
exit;
end;
end;
procedure TForm1.FormCreate(Sender: TObject); // задает части в интерфейсе
var
i: integer;
begin
StringGrid1.Cells[0, 0] := 'часть';
for i:= 1 to CHCount do
begin
StringGrid1.Cells[0, i] := CH[i];
StringGrid1.Cells[i, 0] := CH[i];
Listbox1.Items[i-1] := CH[i];
end;
end;
procedure TForm1.StraightWay; // находит прямой путь
var
i : integer;
begin
for i:= 1 to CHCount do
begin
if Weights[first, i] <> 0 then
Memo1.lines.Add(ListBox1.Items[first] + '=>' + INtToStr(i) +
'(' + IntToStr(Weights[first, i]) + ')');
end;
end;
procedure TForm1.GoCount; // находит непрямой путь между частями и вычисляет расстояние
var
i, n, j : integer;
str : string;
begin
n := 0;
str := (ListBox1.Items[first] + '=>');
for j := 1 to CHCount do
begin
for i := 0 to CHCount-1 do
begin
if Weights[first, i] <> 0 then
if Weights[i, j] <> 0 then
begin
n := n + Weights[first, i] + Weights[i, j];
str := str + ListBox1.items[i] + '=>';
end;
end;
Memo1.Lines.Add(str + IntToStr(j) + '('+IntToStr(n)+')')
end;
end;
procedure TForm1.Button1Click(Sender: TObject); // очистка
var
i, j: integer;
begin
for i:= 1 to CHCount do
for j:= 1 to CHCount do
begin
StringGrid1.Cells[j, i] := '';
end;
Memo1.Lines.Clear;
end;
end.
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 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 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22<
, устанавливаем метку вершины 4 равной 22.
Ещё один сосед вершины 2 — вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.
Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем ее как посещенную.
Третий шаг
. Повторяем шаг алгоритма, выбрав вершину 3. После ее «обработки» получим такие результаты:
Дальнейшие шаги
. Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).
Завершение выполнения алгоритма
. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.
содержание ..
263
264
265 ..
|
|