Программа "Определение кратчайшего пути в графе" - Определение кратчайшего пути в графе
Программа "Определение кратчайшего пути в графе" разработана в среде "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.
Рабочее поле программы предназначено для визуального ввода графов.
Рабочее поле с введенным графом выглядит следующим образом:
Похожие статьи
-
2.2 Нахождение кратчайших путей в графе - Определение кратчайшего пути в графе
Начальные понятия Будем рассматривать ориентированные графы G = < V , E> , дугам которых приписаны веса. Это означает, что каждой дуге < U ,...
-
1.2 Основные термины и теоремы теории графов - Определение кратчайшего пути в графе
1. Граф - Пара объектов G = ( X, Г ),где Х - конечное множество, а Г - конечное подмножество прямого произведения Х*Х. При этом Х называется множеством...
-
Теория Графов, 1.1 Историческая справка - Определение кратчайшего пути в графе
Граф дискретный программирование 1.1 Историческая справка ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический...
-
Для проведения тестов была написана программа задания единичного интервального графа. Входные параметры: число вершин, длина отрезка на котором задается...
-
Задачи на графах, 2.1 Описание различных задач на графах - Определение кратчайшего пути в графе
2.1 Описание различных задач на графах Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех...
-
Программа реализует алгоритм четырех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным,...
-
Программа задания случайных графов Эрдеша - Реньи - Алгоритмы нескольких махов
Программа реализует алгоритм задания случайных графов Эрдеша - Реньи. В качестве входных параметров задаются число вершин и число ребер. Вершины ребер...
-
Введение - Определение кратчайшего пути в графе
Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера...
-
Основные определения, термины и понятия - Визуализация графа цитирования
1. Граф - совокупность множества вершин и наборов пар вершин, называемых ребрами. 2. Ориентированный граф - граф в котором пары вершин в ребрах...
-
Входные параметры: входной файл, выходной файл, номер вершины, номер вершины. Если задаваемые номера вершин положительные, то добавляется соответствующее...
-
3.1 Язык программирования Delphi Delphi - язык и среда программирования, относящаяся к классу RAD - (Rapid Application Development _ "Средство быстрой...
-
Заключение - Разработка программы для реализации редактора временных графов синхронизации
Результатом выполнения задания является реализованный редактор временных графов синхронизации (класс временных сетей Петри), соответствующий задачам,...
-
Чтобы построить граф цитирования из библиотеки IEEE Xplore Digital Library используется следующий метод. Выбирается статья из библиотеки, далее...
-
Сравнение аналогов - Разработка программы для реализации редактора временных графов синхронизации
Поскольку конечной целью работы был редактор сетей Петри, интегрированный с внешней библиотекой алгебраических вычислений, было рациональным рассмотреть...
-
Клиентская программа, Инструменты разработки - Визуализация графа цитирования
Клиентская программа - является основной частью программы, так как она реализует все алгоритмы, описанные в главе 2 данного документа. Несмотря на то,...
-
ОПРЕДЕЛЕНИЕ АРХИВАЦИИ - Архивация информации и программы-архиваторы
Существует множества определений понятия Архивация , вот некоторые из них: Архивация - сжатие информации для уменьшения ее объема Архивация - помещение...
-
Библиотека GridMD поддерживает три механизма определения действий, связываемых с узлами графа [8]. Узел графа может соответствовать исполнению стороннего...
-
Поиск кратчайшего пути в лабиринте на языке Си
Лабораторная работа № 3 Поиск кратчайшего пути в лабиринте на языке Си Формулировка задания Найти кратчайший путь в лабиринте от текущего положения до...
-
Сеть Петри это двудольный направленный граф с маркировкой, ребра которого задают причинно-следственные отношения "события-условия" и именуются дугами....
-
Алгоритм для определения силы комбинации - Программа построения равновесных стратегий для игры
В играх типа Omaha для определения силы комбинации необходимо учитывать 9 карт: 4 стартовых карты игрока и 5 общих карт. По стандартным правилам покера...
-
6.2.2.1 Расчет основной заработной платы Расходы по этой статье состоят из планового фонда заработной платы всех категорий работников, занятых в...
-
Множество D с двумя заданными на нем операциями (плюс) и (умножение) называется диоидом, если выполнены следующие аксиомы: § Ассоциативность. §...
-
Серверная программа, Инструменты разработки - Визуализация графа цитирования
Серверная программа - это веб-сервер, необходимый для получения и хранения графов. Сервер может создавать графы цитрования из библиотеки IEEE Xplore...
-
SIW (System Information for Windows) -- это условно-бесплатная утилита, которая предоставляет пользователям мощный и простой в использовании инструмент...
-
Приложение разрабатывается в соответствии с паттерном проектирования Model-View-Presenter (MVP), который является производным от Model-View-Controller...
-
Стек технологий При выборе стека технологий основное внимание уделялось следующим факторам, в порядке убывания значимости: § Кроссплатформенность; §...
-
Обоснование выбранного метода При дизайне системы согласно требованиям или при оптимизации существующей необходимо ввести модель, позволяющую не только...
-
Литература - Разработка программы для реализации редактора временных графов синхронизации
1. Авдошин С. М. Оптимизация гибких производственных систем // 1987. 2. Лескин А. А. Алгебраические модели гибких производственных систем // 1986. 3....
-
Существующие решения - Визуализация графа цитирования
На данный момент не было найдено решений, которые полностью бы удовлетворяли всем требованиям, однако существуют те, которые реализуют их не все и/или не...
-
Постановка задачи - Визуализация графа цитирования
В качестве результата выпускной квалификационной работы требуется создать программу, позволяющую визуализировать граф цитирования публикаций, которые...
-
Граф переходов конечного автомата лексического анализатора Исходная КС-грамматика G({prog, end., if, else, then, begin, end, while, do, or, and, not,...
-
20. Пользователь через UI инициирует создание определения 21. Приложение получает данные описывающие определение и изменяет свое состояние 22. Приложение...
-
Постановка задачи, Описание программы, Алгоритм работы - Алгоритм кодировки RSA
Реализовать клиент серверное приложение для пересылки закодированной информации. В качестве алгоритма реализовать алгоритм RSA. Описание программы...
-
Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов
Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное...
-
Поворот точки относительно центра на заданный угол: X = o. X + (p. X-o. X) * cos(angle) - (p. Y-o. Y) * sin(angle) Y = o. Y + (p. X-o. X) * sin(angle) +...
-
Пример с tegview ¦ L-- qml ¦ +-- tegrender. js ¦ L-- tegview. qml +-- tegview ¦ +--...
-
Работа локальной сети Использование команды ipconfig для определения ip-адреса компьютера. Internet основан на семействе протоколов tcp/ip, определяющих,...
-
Введение - Разработка программы для реализации редактора временных графов синхронизации
Математическое моделирование дискретно-событийных динамических систем является относительно молодым направлением науки теории управления. Разработка...
-
Общие сведения Наименование программы. "Статистические Диаграммы". Формулировка задачи. Дано n целых чисел (n-четное число) x1,x2,...xn/2 Yn/2+1,...
-
Данная программа предназначена для работы в среде MSDOS. По окончании вычислений программа автоматически освобождает ресурсы ЭВМ завершая свою работу. По...
Программа "Определение кратчайшего пути в графе" - Определение кратчайшего пути в графе