Метод Дейкстры нахождения кратчайшей цепи в связном графе

• Введение
• 1. Теоретическая часть
• 1.1 Основные понятия теории графов
• 1.2 Связность графов
• 1.3 Задача о кратчайшей цепи
• 1.4 Метод Дейкстры нахождения кратчайшей цепи в связном графе
• 2. Реализация метода
• 2.1 Программная реализация метода Дейкстры
• 2.2 Описание логики программного модуля
• 2.3 Примеры работы программы
• Заключение
• Список использованных источников
• Приложение 1: Текст программы
• Приложение 2: графы тестовых расчетов

История человечества насчитывает много миллионов лет. На всей ее протяженности люди сталкиваются с задачами, требующими от них принятия оптимальных решений: как лучше всего распределить ресурсы, как проложить дорогу между селами с минимальными затратами сил и средств и так далее. Еще в прошлом веке, до появления ЭВМ, решение проблем оптимизации было сложной и трудоемкой задачей.

Теперь, когда в распоряжении у человека имеется компьютер, обладающий колоссальными вычислительными возможностями, находить решения разнообразных математических, физических, экономических задач, в том числе и задач оптимизации, стало гораздо проще и приятнее. Достаточно указать ЭВМ то, что мы хотим получить, и через мгновение она уже может выдать ответ!

В работе речь пойдет о методе Дейкстры нахождения кратчайшей цепи в связанном графе. Этот метод сочетает в себе элегантность мысли и высочайшую эффективность. Также проводится его сравнение с методом простого перебора.

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

1. Теоретическая часть

1.1 Основные понятия теории графов

Если необходимо представить в наглядной форме систему каких-либо взаимосвязанных объектов, то прибегают к такому построению: на плоскости или в пространстве выбирается несколько точек и некоторые пары точек соединяются линиями.

Объект, который получается в результате указанного построения, называется графом. В качестве примеров можно указать блок-схему алгоритма, граф соединений в электрической схеме, сеть путей дорожного сообщения и так далее.

Одну и ту же систему объектов и связей между ними можно по-разному изобразить, применяя указанное выше построение: различным образом располагать точки, в качестве соединяющих их линий брать те или иные кривые и так далее. Более того, можно вообще не рисовать, а указать систему связей объектов в какой-либо иной форме, например, в словесной. Это рассуждение показывает, что необходимо определение графа, как некоторого формального объекта, который можно различными способами представать наглядно.

Говорят, что задан конечный неориентированный граф, если заданы следующие два объекта [1]:

1) конечное множество, элементы этого множества называются вершинами графа;

2) Некоторое множество неупорядоченных пар элементов из, это множество обозначается, его элементы, то есть пары вершин, называются ребрами.

метод дейкстра связный граф Тот факт, что граф определяется парой множеств и, записывается в виде. При наглядном представлении графа вершины изображаются точками, ребра — линиями, соединяющими эти точки.

Например,, где

.

В наглядной форме этот граф представлен на рисунке ниже.

Наряду с введенным определением графа возможны и другие. Так, например, иногда возникает необходимость рассматривать графы, в которых одну и ту же пару вершин соединяет несколько ребер. Такие графы называют мультиграфами. Рассматривают также графы, в которых некоторые ребра могут иметь совпадающие концы. Такие ребра называют петлями. В большинстве приложений теории графов можно отбрасывать петли и заменять кратные ребра одним ребром. В дальнейшем под графом будем понимать конечный неориентированный граф без петель и кратных ребер.

Понятие ориентированного графа возникает, если ребрам графа придать направление, ориентацию, так что один из концов ребра будет началом, а другой — концом.

Говорят, что задан ориентированный граф, если указаны два объекта:

1) непустое конечное множество — вершины графа;

2) множество, составленное из упорядоченных пар вершин.

Элементы множества называют дугами. Дуга ориентированного графа изображается отрезком со стрелкой.

Пусть дан граф. О ребре этого графа говорят, что оно соединяет вершины и. Вершины, соединенные ребром, называются смежными. О ребре и вершине говорят, что они инцидентны, то же можно сказать о ребре и вершине .

Будем обозначать число вершин графа буквой, а число ребер — буквой:. Это основные числовые характеристики графа.

Число ребер, инцидентных данной вершине, называется степенью этой вершины и обозначается. Вершина, у которой степень равна нулю, называется изолированной. Вершины, имеющие степень, равную единице, называют висячими. Например, вершины и на рисунке, изображенном ранее, висячие, а вершина — изолированная.

Справедливы следующие утверждения:

сумма степеней всех вершин графа равна удвоенному числу ребер;

число вершин, имеющих нечетную степень, четно.

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

Граф, не имеющий ребер, называется пустым. Все вершины пустого графа изолированные. Граф, в котором каждая пара вершин соединена ребром, называется полным. Полныйвершинный граф обозначается, для каждой его вершины имеем .

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

Граф называется подграфом графа, если и .

Граф называется остовным подграфом графа, если и. Остовный подграф получается, если в графе удалить часть ребер, не трогая вершин.

Не всегда удобно задавать граф в том виде, как это указано в определении. Например, при обработке графа на ЭВМ, его удобно представлять в матричной форме.

Пусть дан ориентированный граф и. Занумеруем вершины графа числами. Рассмотримматрицу, элементы которой определяются по следующему правилу:, если, в противном случае .

Матрица называется матрицей смежности вершин графа. Для случая графа эта матрица симметрична и имеет нули на диагонали.

Число единиц в какой-либо строке матрицы смежности равно степени соответствующей вершины.

При введении какого-либо математического понятия всегда договариваются о том, какие объекты считаются одинаковыми и какие необходимо различать. Изоморфные объекты — это такие объекты, которые в дальнейшей теории не различаются и рассматриваются как один объект. Например, графы, показанные на рисунке ниже, отличаются только обозначением вершин и способом размещения на плоскости.

Если во втором графе переобозначить вершины по схеме

то множества вершин и ребер в первом и во втором графах совпадут, и получится один и тот же граф.

Графы и называются изоморфными, если между множествами их вершин можно установить взаимно однозначное соответствие, такое, что любые две вершины смежны в одном из графов в том и только в том случае, когда соответствующие им вершины смежны в другом графе.

На рисунке выше изображены два изоморфных графа.

1.2 Связность графов

Пусть — граф. Конечная последовательность вершин и ребер графа

в которой каждое есть ребро, соединяющее вершины и, называется маршрутом на графе .

Говорят, что маршрут (1.1) соединяет вершины и. Число называют длиной маршрута. Таким образом, длина — это количество ребер, входящих в маршрут. Маршрут называется замкнутым, если .

Маршрут, в котором все ребра различны, называется цепью. Замкнутая цепь называется циклом.

Цепь называется простой, если все ее вершины различны. Простой цикл — это цикл, в котором все вершины, кроме первой и последней, различны.

В графе, показанном на рисунке выше,

— маршрут,

— цепь,

— простая цепь.

Пусть в графе имеется маршрут, соединяющий вершины и. Если часть маршрута вида

содержащую дважды вершину, заменить на

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

Граф называется связным, если любые две его вершины можно соединить цепью.

Рассмотрим произвольный граф, пусть — некоторая вершина. Обозначим через множество вершин графа, которые можно соединить цепью с вершиной. Если данный граф связный, то, в противном случае .

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

Пусть. Тогда — связный граф. Действительно, пусть,. Соединяя цепь от к с цепью от к, получим маршрут, соединяющий и. Как отмечалось, этот маршрут можно преобразовать в цепь.

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

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

такие что

Другими словами, графы связаны, не имеют общих вершин и ребер, а каждая вершина и каждое ребро исходного графа принадлежит одному из этих графов.

Графы называются компонентами связности графа. Число — еще одна числовая характеристика графа, указывающая, сколько компонент связности он содержит. Для связного графа, если граф несвязный, то .

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

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

Введенное расстояние удовлетворяет следующим аксиомам метрики:

1); ;

2) ;

3) .

Диаметром графа называется величина

где максимум берется по всевозможным парам вершин графа.

Определим для каждой вершины графа величину

то есть расстояние от до самой далекой от нее вершины графа. Минимум этой величины по всем вершинам графа называется радиусом графа :

.

Вершина, в которой достигается этот минимум:, называется центральной.

1.3 Задача о кратчайшей цепи

При вычислении расстояний между вершинами графа необходимо решать следующую задачу [3]: в связном графе заданы две вершины и; найти цепь наименьшей длины, то есть кратчайшую цепь, связывающую с .

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

Пометим вершину отметкой «0». Все вершины, смежные с вершиной, пометим отметкой «1». Непомеченные вершины, смежные с ними — отметкой «3» и так далее, пока не будет помечена вершина. Допустим, что вершина получила отметку. Возвращаемся от к, отыскивая последовательно: смежную с вершину, имеющую отметку, смежную с вершину, имеющую отметку и так далее до тех пор, пока из некоторой вершины с отметкой «1», не придем в вершину. Цепь искомая, она имеет длину .

Описанный выше алгоритм называют волновым: процесс расстановки отметок напоминает распространение возмущения, которое возникает в вершине и движется со скоростью одно ребро в единицу времени; вершины, имеющие одинаковые отметки, представляют собой фронт волны.

Рассмотрим теперь обобщение задачи о кратчайшей цепи — это задача о кратчайшей цепи в графе с нагруженными ребрами.

Поставим в соответствие каждому ребру графа целое неотрицательное число и будем называть его длиной ребра. Объект, который при этом получается, называют графом с нагруженными ребрами, он обозначается. Длиной цепи в таком графе назовем сумму длин входящих в цепь ребер и вновь рассмотрим задачу об отыскании цепи наименьшей длины между двумя заданными вершинами и .

Как и предыдущий, алгоритм решения этой задачи состоит в вычислении по определенным правилам числовых отметок вершин. Отметку вершины будем обозначать через, кроме того, для длины ребра наряду с обозначением будем использовать обозначение .

После окончания процесса вычисления отметок они должны удовлетворять определенным требованиям — условиям оптимальности. Эти условия сформулированы в следующем утверждении.

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

1) ;

2) Для каждого ребра

3) ;

4) Для каждой вершины найдется смежная с ней вершина, такая то

.

Тогда:

длина кратчайшей цепи между вершинами и равна ;

сама кратчайшая цепь проходит по вершинам

, таким что .

Для доказательства заметим, что цепь (1.2), о которой говорится в утверждении, можно построить, используя свойство 3). Для этого надо, начав с вершину, найти смежную ей вершину, для которой

;

Далее найти смежную с вершину, для которой выполняется свойство 3), то есть разность отметок вершин и равна длине соединяющего их ребра. Построение продолжаем до попадания в вершину .

Длина построенной цепи равна

.

Покажем, что длина любой другой цепи между вершинами и не меньше, чем. Пусть

произвольная из таких цепей.

В силу свойства отметок 2) для ребер цепи (1.3) выполняются следующие неравенства:

Сложив эти неравенства, получим

то есть длина цепи не меньше, чем .

Утверждение доказано.

1.4 Метод Дейкстры нахождения кратчайшей цепи в связном графе

Рассмотрим подробно метод Дейкстры нахождения кратчайшей цепи в связном графе, обеспечивающий эффективное ее отыскание путем присвоения вершинам графа отметок, удовлетворяющих свойствам 1) — 3).

Алгоритм состоит из двух этапов:

начальная расстановка отметок;

циклически повторяющаяся процедура исправления отметок.

На каждом шаге алгоритма все отметки делятся на предварительные и окончательные. Алгоритм обрабатывает только предварительные отметки и заканчивает работу, когда все отметки станут окончательными.

Описание алгоритма Дейкстры [4]:

Начальная расстановка отметок.

Полагаем

.

Все отметки объявляем предварительными.

Исправление отметок.

Среди всех предварительных отметок находим наименьшую. Пусть это отметка вершины. Для каждой вершины, смежной с и имеющей предварительную отметку, исправляем по следующему правилу:

.

После исправления отметок всех смежных с вершин объявляем отметку вершины окончательной.

Как видно из описания алгоритма, каждый шаг исправления отметок делает одну из них окончательной. Таким образом, шаг исправления отметок будет выполняться раз, где — число вершин графа. Окончательные отметки всегда удовлетворяют условиям оптимальности 1) — 3).

Кратчайшая цепь начинает строиться из конечной вершины. Отыскиваем смежную с вершиной вершину, причем такую, для которой равно длине ребра между этими вершинами. Указанное ребро будет входить в кратчайшую цепь. Переходим к вершине и производим для нее те же операции, и так до тех пор, пока не дойдем до вершины. Построенная цепь будет оптимальной (кратчайшей).

Проведем сравнение метода Дейкстры с методом прямого поиска.

Метод прямого поиска кратчайшей цепи в связном графе сводится к последовательному перебору всевозможных цепей, ведущих от вершины к вершине. Для графов размера и этот метод более эффективен, потому что поиск в графе размера он производит поиск кратчайшей цепи всего за 2 шага (метод Дейкстры за 4), в графе размера он производит поиск кратчайшей цепи за 4 шага (метод Дейкстры за 6). Однако с дальнейшим увеличением числа вершин эффективность метода прямого перебора катастрофически падает. Число вариантов возрастет по экспоненциальному закону. Например, для графа, имеющего 30 вершин, методом прямого поиска нужно сделать операций, где 49 — число ребер, а метод Дейкстры произведет всего лишь 30 операций! Эффективность очевидна и видна невооруженным глазом.

2. Реализация метода

2.1 Программная реализация метода Дейкстры

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

Для графа применяем алгоритм Дейкстры нахождения кратчайшей цепи от вершины к вершине .

Начальная расстановка отметок.

Полагаем

.

В качестве бесконечности принимаем очень большое число, такое, которое во много раз больше любой из длин ребер в исследуемом графе.

Все отметки объявляем предварительными.

Исправление отметок.

Среди всех предварительных отметок находим наименьшую. Пусть это отметка вершины. Для каждой вершины, смежной с и имеющей предварительную отметку, исправляем по следующему правилу:

.

После исправления отметок всех смежных с вершин объявляем отметку вершины окончательной.

Затем проводим построение кратчайшей цепи, стартую от вершины и заканчивая вершиной .

2.2 Описание логики программного модуля

Листинг программы приведен в приложении 1. Ниже будут описаны функции программного модуля и их назначение.

Функция main () является базовой. Она реализует алгоритм метода Дейкстры, описанного в предыдущих разделах работы.

Функция search_min_versh () производит поиск наименьшей вершины, имеющей предварительную отметку. Производится сквозное сканирование по всем вершинам графа, имеющих предварительные отметки и выбор наименьшей из них.

Функция setup_preview_values (x, y) расстанавливает отметки для вершин, смежных с вершиной графа.

Функция print_graph () производит вывод на экран графа, используя для этого графический режим, а также указывает на нем кратчайшую цепь.

Функция print_title () предназначена для вывода названия программы на дисплей.

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

Программа GRISHA-Corp. Optimal Way Searcher v1.02 Professional написана на языке программирования высокого уровня Borland C++ 3.1 в виде приложения MS-DOS. Обеспечивается полная совместимость программы со всеми широко известными операционными системами корпорации Майкрософт: MS-DOS 5. x,

6. xx,

7. xx,

8. xx, Windows 9x/Me/2000/NT/XP. Программа может производить расчеты графов размером до вершин, однако вывод на экран возможен только для графов размером и меньше. Минимальный размер графа, который обрабатывается программой — это. Если размеры графа слишком велики и его нельзя отобразить на дисплее, пользователь может воспользоваться специально создаваемым файлом graf. txt из корневой директории программы. В нем указана вся подробная информация о графе, окончательные отметки вершин, а также кратчайшая цепь в виде цепочки вершин. Файл graf. txt создается автоматически при каждом выполнении программы. Его можно просмотреть любым текстовым редактором, например NotePad или Shtirlitz.

2.3 Примеры работы программы

В качестве примеров рассмотрим отыскание кратчайшей цепи в нескольких связных прямоугольных графах. На рисунках из приложения 2 изображены графы с нанесенными на них окончательными отметками, длинами ребер и кратчайшей цепью. Цепь выделена жирной линией. Изображения созданы самой программой ILYA-Corp. Optimal Way Searcher v1.02 Professional.

Заключение

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

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

Список использованных источников

1. Аттетков А. В., Галкин С. В., Зарубин В. С. Методы оптимизации. — М.: Издательство МГТУ им. Н. Э. Баумана, 2001. — 440 с.

2. Берж К. Теория графов и ее применение. — М.: Мир, 1962. — 512 с.

3. Глаголев В. В. Методы дискретной математики. — Тула: ТулГУ, 2000. — 232 с.

4. Н. Кристофедс. Теория графов. Алгоритмический подход. — М.: Мир, 1977. — 432 с.

5. Ху Т., Целочисленное программирование и потоки в сетях. — М.: Мир, 1974. — 457 с.

Приложение 1: Текст программы

// - ——————————————————————————————————- - //

#include

#include

#include

#include

#define INFTY 32 766 // Имитация бесконечности

#define VERSION 1.02 // Версия программы

int min_x; // Минимум по x

int min_y; // Минимум по y

int lengths_hor [50]; // Массив длин горизонтальных ребер

int lengths_vert [50]; // Массив длин вертикальных ребер

int values [51]; // Массив числовых отметок вершин графа

short remarks [51]; // Массив отметок вершин графа (0-preview, 2-final)

int min_value; // Минимальное значение (расстояние между вершинами)

int i, j; // Служебные переменные для использования в циклах

int n = 2; // Количество вершин в графе по горизонтали

int m = 2; // Количество вершин в графе по вертикали

int x, y; // Переменные для отыскания кратчайшего пути

int temp; // Временная служебная переменная

FILE *myfile; // Файл

int search_min_versh (void); // Поиск наименьшей вершины

void setup_preview_values (int x, int y); // Расстановка предв. отметок

void print_title (void); // Печать названия программы

void print_graph (); // Печать графа

void main (void); // Главная функция

// - ——————————————————————————————————- - //

void main (void)

{

int gdriver = DETECT, gmode, errorcode;

int xmax, ymax;

// Инициализация графики и локальных переменных

initgraph (&gdriver, &gmode, «»);

// Чтение результата инициализации

errorcode = graphresult ();

// В случае обнаружения ошибки

if (errorcode! = grOk)

{

printf («Ошибка инициализации графики: %s. n», grapherrormsg (errorcode));

printf («Нажмите любую клавишу для завершения. «);

getch ();

exit (1);

}

clrscr ();

cleardevice ();

textcolor (0);

setbkcolor (0);

clrscr ();

cleardevice ();

print_title ();

label1: printf («Укажите количество вершин в графе по горизонтали: «);

scanf («%d», &n);

if (n < 2 || n > 50)

{

printf («ОШИБКА! Укажите величину в диапазоне 2.50! n»);

goto label1;

}

label2: printf («Укажите количество вершин в графе по вертикали: «);

scanf («%d», &m);

if (m < 2 || m > 50)

{

printf («ОШИБКА! Укажите величину в диапазоне 2.50! n»);

goto label2;

}

clrscr ();

cleardevice ();

print_title ();

printf («Приготовьтесь формировать граф с %dx%d вершинами. n», n, m);

printf («Сейчас вводите длины, соответствующие горизонтальным ребрам графа. nn»);

for (j = 1; j <= m; j++)

{

for (i = 1; i <= n — 1; i++)

{

label5: printf («Ребро между вершиной (%d,%d) и (%d,%d) равно:», i, j, i + 1, j);

scanf («%d», &temp);

if (temp < 1)

{

printf («ОШИБКА! Длина ребра задана неверно! n»);

goto label5;

}

lengths_hor [i] [j] = temp;

}

}

clrscr ();

cleardevice ();

print_title ();

printf («Сейчас вводите длины, соответствующие вертикальным ребрам графа. nn»);

for (j = 1; j <= m — 1; j++)

{

for (i = 1; i <= n; i++)

{

label6: printf («Ребро между вершиной (%d,%d) и (%d,%d) равно:», i, j, i, j + 1);

scanf («%d», &temp);

if (temp < 1)

{

printf («ОШИБКА! Длина ребра задана неверно! n»);

goto label6;

}

lengths_vert [i] [j] = temp;

}

}

printf («Построение графа завершено. Находим кратчайший путь от (1,1) к (%d,%d). nn», n, m);

if (n > 8 || m > 7)

{

printf («nРазмеры графа слишком велики для корректного отображения на экране. n»);

printf («Вы можете воспользоваться созданным файлом graf. txt. n»);

printf («nДля выхода нажмите ENTER. «);

x = n;

y = m;

fprintf (myfile, «-> Кратчайшую цепь в графе образуют вершины: n»);

fprintf (myfile, «(%d,%d) — >», x, y);

label3_:

if (x == 1 && y == 1)

{

goto label4_;

}

else

{

// шаг вверх

if (values [x] [y] - values [x] [y — 1] == lengths_vert [x] [y — 1] && y >= 2)

{

fprintf (myfile, «(%d,%d) — >», x, y — 1);

y = y — 1;

}

// шаг вниз

if (values [x] [y] - values [x] [y + 1] == lengths_vert [x] [y] && y <= m — 1)

{

fprintf (myfile, «(%d,%d) — >», x, y + 1);

y = y + 1;

}

// шаг влево

if (values [x] [y] - values [x — 1] [y] == lengths_hor [x — 1] [y] && x >= 2)

{

fprintf (myfile, «(%d,%d) — >», x — 1, y);

x = x — 1;

}

// шаг вправо

if (values [x] [y] - values [x + 1] [y] == lengths_hor [x] [y] && x <= n — 1)

{

fprintf (myfile, «(%d,%d) — >», x + 1, y);

x = x + 1;

}

}

goto label3_;

label4_:

fprintf (myfile, «n->Конец»);

fclose (myfile);

while (getch ()! = 13);

exit (0);

}

// Устанавливаем предварительные отметки для каждой вершины графа,

// а также предварительные значения расстояний в 'бесконечность'

for (j = 1; j <= m; j++)

{

for (i = 1; i <= n; i++)

{

remarks [i] [j] = 0;

values [i] [j] = INFTY;

}

}

// Начальная вершина должна иметь отметку, меньшую бесконечности (например, 0)

values [1] = 0;

min_x = 1;

min_y = 1;

// Расстанавливаем отметки до тех пор, пока они все не станут окончательными

while (1)

{

setup_preview_values (min_x, min_y);

if (search_min_versh () == - 1)

{

break;

}

}

printf («Кратчайший путь вычислен, ОК!»);

clrscr ();

cleardevice ();

// Чертим граф

gotoxy (1,2);

print_graph ();

// Чертим кружочки

for (j = 1; j <= m; j++)

{

for (i = 1; i <= n; i++)

{

setcolor (7);

circle (i * 72 — 16, j * 65 — 44, 15);

}

}

// Чертим горизонтальные ребра

for (j = 1; j <= m; j++)

{

for (i = 1; i <= n — 1; i++)

{

setcolor (15);

line (i * 72, j * 65 — 44, i * 72 +40, j * 65 — 44);

}

}

// Чертим вертикальные ребра

for (j = 1; j <= m — 1; j++)

{

for (i = 1; i <= n; i++)

{

setcolor (15);

line (i * 72 — 16, j * 65 — 28, i * 72 — 16, j * 65 + 6);

}

}

// Наносим длины вертикальных ребер в графе

for (j = 1; j <= m — 1; j++)

{

for (i = 1; i <= n; i++)

{

gotoxy (i * 9, j * 4);

printf («%d», lengths_vert [i] [j]);

}

}

// Наносим длины горизонтальных ребер в графе

for (j = 1; j <= m; j++)

{

for (i = 1; i <= n — 1; i++)

{

gotoxy (i * 9 + 3, j * 4 — 3);

printf («%d», lengths_hor [i] [j]);

}

}

// Теперь необходимо указать кратчайший путь

x = n;

y = m;

fprintf (myfile, «-> Кратчайшую цепь в графе образуют вершины: n»);

fprintf (myfile, «(%d,%d) — >», x, y);

label3:

if (x == 1 && y == 1)

{

goto label4;

}

else

{

// шаг вверх

if (values [x] [y] - values [x] [y — 1] == lengths_vert [x] [y — 1] && y >= 2)

{

fprintf (myfile, «(%d,%d) — >», x, y — 1);

gotoxy (1,12);

y = y — 1;

// замулевать ребро верт_ (x, y)

setcolor (2);

line (x * 72 — 16, y * 65 — 28, x * 72 — 16, y * 65 + 6);

line (x * 72 — 17, y * 65 — 28, x * 72 — 17, y * 65 + 6);

line (x * 72 — 15, y * 65 — 28, x * 72 — 15, y * 65 + 6);

}

// шаг вниз

if (values [x] [y] - values [x] [y + 1] == lengths_vert [x] [y] && y <= m — 1)

{

fprintf (myfile, «(%d,%d) — >», x, y + 1);

y = y + 1;

// замулевать ребро верт_ (x, y — 1)

setcolor (2);

line (x * 72 — 16, (y — 1) * 65 — 28, x * 72 — 16, (y — 1) * 65 + 6);

line (x * 72 — 17, (y — 1) * 65 — 28, x * 72 — 17, (y — 1) * 65 + 6);

line (x * 72 — 15, (y — 1) * 65 — 28, x * 72 — 15, (y — 1) * 65 + 6);

}

// шаг влево

if (values [x] [y] - values [x — 1] [y] == lengths_hor [x — 1] [y] && x >= 2)

{

fprintf (myfile, «(%d,%d) — >», x — 1, y);

x = x — 1;

// замулевать ребро гор_ (x, y)

setcolor (2);

line (x * 72, y * 65 — 44, x * 72 + 40, y * 65 — 44);

line (x * 72, y * 65 — 45, x * 72 + 40, y * 65 — 45);

line (x * 72, y * 65 — 43, x * 72 + 40, y * 65 — 43);

}

// шаг вправо

if (values [x] [y] - values [x + 1] [y] == lengths_hor [x] [y] && x <= n — 1)

{

fprintf (myfile, «(%d,%d) — >», x + 1, y);

x = x + 1;

// замулевать ребро гор_ (x — 1, y)

setcolor (2);

line ((x — 1) * 72, y * 65 — 44, (x — 1) * 72 + 40, y * 65 — 44);

line ((x — 1) * 72, y * 65 — 45, (x — 1) * 72 + 40, y * 65 — 45);

line ((x — 1) * 72, y * 65 — 43, (x — 1) * 72 + 40, y * 65 — 43);

}

}

goto label3;

label4:

fprintf (myfile, «n->Конец»);

fclose (myfile);

gotoxy (1, 25);

printf («Для выхода нажмите ENTER. «);

while (getch ()! = 13);

clrscr ();

cleardevice ();

printf («ILYA Corporation Soft Group FOREVER! n»);

printf («ilya-corp@mail.run»);

printf («http://ilya-corp. narod. run»);

closegraph ();

}

// - ——————————————————————————————————- - //

int search_min_versh (void)

{

// Функция отыскивает минимальную вершину с предварительной отметкой

int s = INFTY;

int success = 0;

for (j = 1; j <= m; j++)

{

for (i = 1; i <= n; i++)

{

if (remarks [i] [j] == 0 && values [i] [j] < s)

{

s = values [i] [j];

min_x = i;

min_y = j;

success = 1;

}

}

}

if (success == 0)

{

min_x = - 1;

min_y = - 1;

return — 1;

}

return 1;

}

// - ——————————————————————————————————- - //

void setup_preview_values (int x, int y)

{

// Функция расстанавливает значения для смежных вершин графа

if (remarks [x — 1] [y] == 0 && x — 1 >= 1)

{

if (values [x — 1] [y] > values [x] [y] + lengths_hor [x — 1] [y])

{

values [x — 1] [y] = values [x] [y] + lengths_hor [x — 1] [y];

}

}

if (remarks [x + 1] [y] == 0 && x + 1 <= n)

{

if (values [x + 1] [y] > values [x] [y] + lengths_hor [x] [y])

{

values [x + 1] [y] = values [x] [y] + lengths_hor [x] [y];

}

}

if (remarks [x] [y + 1] == 0 && y + 1 <= m)

{

if (values [x] [y + 1] > values [x] [y] + lengths_vert [x] [y])

{

values [x] [y + 1] = values [x] [y] + lengths_vert [x] [y];

}

}

if (remarks [x] [y — 1] == 0 && y — 1 >= 1)

{

if (values [x] [y — 1] > values [x] [y] + lengths_vert [x] [y — 1])

{

values [x] [y — 1] = values [x] [y] + lengths_vert [x] [y — 1];

}

}

remarks [x] [y] = 1;

}

// - ——————————————————————————————————- - //

void print_graph ()

{

// Просто вывод матрицы значений вершин

myfile = fopen («graf. txt», «w+»);

fprintf (myfile, «GRISHA-Corp Optimal Way Searcher v%g Professionaln», VERSION);

fprintf (myfile, «=======================================n»);

fprintf (myfile, «-> Граф имеет размер %dx%dn», n, m);

fprintf (myfile, «-> Граф связный: Даn»);

fprintf (myfile, «-> Задача: поиск кратчайшей цепи в графеn»);

fprintf (myfile, «-> Длина кратчайшей цепи: %dn», values [n] [m]);

fprintf (myfile, «-> Матрица окончательных отметок вершин: n»);

for (j = 1; j <= m; j++)

{

for (i = 1; i <= n; i++)

{

if (values [i] [j] == INFTY)

{

printf («oo «);

}

else

{

printf («%8d», values [i] [j]);

}

}

printf («nnnn»);

}

for (j = 1; j <= m; j++)

{

for (i = 1; i <= n; i++)

{

fprintf (myfile, «%5d», values [i] [j]);

}

fprintf (myfile, «n»);

}

}

// - ——————————————————————————————————- - //

void print_title ()

{

printf («GRISHA-Corp Optimal Way Searcher v%g Professionaln», VERSION);

printf («________________________________________________________________________________»);

}

// - ——————————————————————————————————- - //

Приложение 2: графы тестовых расчетов