Программа "Определение кратчайшего пути в графе" - Определение кратчайшего пути в графе

Программа "Определение кратчайшего пути в графе" разработана в среде "Delphi", работает под ОС "Windows"-95,98,2000,NT.

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

Интерфейс программы имеет следующий вид:

Верхняя панель кнопок предназначена для редактирования графа.

Кнопка "Загрузить" предназначена для загрузки ранее сохраненного графа из файла.

Кнопка "Сохранить" предназначена для сохранения графа в файл.

Кнопка "Переместить" предназначена для перемещения вершин графа.

Кнопка "Удалить" предназначена для удаления вершин графа.

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

Кнопка "Помощь" вызывает помощь программы.

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

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

Окно настроек выглядит следующим образом:

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

При включенной кнопке "Показывать сетку" отображается сетка для удобства ввода вершин.

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

При включенной кнопке "Выравнивать по сетке" новые вершины будут автоматически выравниваться по координатной сетке.

Если выбрать две различные вершины (щелчком левой кнопки мыши) и нажать на кнопку, то программа найдет кратчайший путь между вершинами.

Алгоритм определения кратчайшего пути между вершинами графа описан следующим модулем программы:

Unit MinLength;

Interface

Uses

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

StdCtrls, IO, Data, AbstractAlgorithmUnit;

Type

TMinLength = class(TAbstractAlgorithm)

Private

StartPoint:integer;

EndPoint:integer;

First:Boolean;

Lymbda:array of integer;

Function Proverka:Boolean;

Public

Procedure Make;

End;

Var

MyMinLength: TMinLength;

Implementation

Uses MainUnit, Setting;

Procedure TMinLength. Make;

Var i, j : integer;

PathPlace, TempPoint:Integer;

Flag:boolean;

Begin

With MyData do begin

StartPoint:=MyIO. FirstPoint;

EndPoint:=MyIO. LastPoint;

SetLength(Lymbda, Dimension+1);

SetLength(Path, Dimension+1);

For i:=1 to Dimension do

Lymbda[i]:=100000;

Lymbda[StartPoint]:=0;

Repeat

For i:=1 to Dimension do

For j:=1 to Dimension do

If Matrix[i, j]=1 then

If ( ( Lymbda[j]-Lymbda[i] ) > MatrixLength[j, i] )

Then Lymbda[j]:=Lymbda[i] + MatrixLength[j, i];

Until Proverka ;

Path[1]:= EndPoint ;

J:=1;

PathPlace:=2;

Repeat

TempPoint:=1;

Flag:=False;

Repeat

If ( Matrix[ Path[ PathPlace-1 ],TempPoint] =1 )and (

Lymbda[ Path[ PathPlace-1] ] =

( Lymbda[TempPoint] + MatrixLength[ Path[PathPlace-1 ], TempPoint] ) )

Then Flag:=True

Else Inc( TempPoint );

Until Flag;

Path[ PathPlace ]:=TempPoint;

Inc( PathPlace );

MyIO. DrawPath(Path[ PathPlace-2 ],Path[ PathPlace -1],true);

// ShowMessage('f');

Until(Path[ PathPlace - 1 ] = StartPoint);

// MyIO. DrawPath(Path[ PathPlace-1 ],Path[ PathPlace ],true);

End;

End;

Function TMinLength. Proverka:Boolean;

Var i, j:integer;

Flag:boolean;

Begin

I:=1;

Flag:=False;

With MyData do begin

Repeat

J:=1;

Repeat

If Matrix[i, j]=1 then

If ( Lymbda[j]-Lymbda[i] )>MatrixLength[j, i]then Flag:=True;

Inc(j);

Until(j>Dimension)or(Flag);

Inc(i);

Until(i>Dimension)or(Flag);

Result:=not Flag;

End;

End;

End.

Рабочее поле программы предназначено для визуального ввода графов.

Рабочее поле с введенным графом выглядит следующим образом:

Похожие статьи




Программа "Определение кратчайшего пути в графе" - Определение кратчайшего пути в графе

Предыдущая | Следующая