Разработка программы, реализующий алгоритм Форда-Беллмана поиска кратчайших путей на нагруженном орграфе

КУРСОВАЯ РАБОТА

Разработка программы, реализующий алгоритм Форда-Беллмана поиска кратчайших путей на нагруженном орграфе.

              Студент:             

              Руководитель:              

              Дата защиты:              .

СОДЕРЖАНИЕ:

1.      Введение              3

2.      Постановка задачи              4

1.     Представление кратчайших путей, релаксация……………………5

3.      Алгоритм Форда-Беллмана              8

1.     Перечень используемых величин и их назначение………………10

2.     Входные и выходные данные, диапазон изменений……………..10

3.     Блок-схема алгоритма...……………………………………………11

4.      Заключение………………………………………………………………..13

5.      Список используемой литературы………………………………………14

6.      Приложение A. Инструкция к использованию программы..…………..15

7.      Приложение B. Код программы………………………………………….17

ВВЕДЕНИЕ

Целью данной курсовой работы, является написание программы, реализующей алгоритм Форда-Беллмана. Алгоритм направлен на нахождение расстояния от источника до всех вершин и нахождение кратчайшего пути из S в T.

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

ПОСТАНОВКА ЗАДАЧИ.

Дан взвешенный орграф G= (V, E), дугам которого приписаны веса, задаваемые матрицей весов  С = (сij), где  сij – действительные числа, определяющие вес дуги между вершинами vi и vj. Если между вершинами дуги нет, то соответствующий элемент матрицы весов считается равным бесконечности. Длиной пути m = (v0, ..., vk) называется сумма весов дуг, входящих в этот путь.

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

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

В некоторых задачах о кратчайшем пути из вершины S веса дуг могут принимать отрицательные значения, т.е. элементы  сij матрицы стоимостей  с  могут быть и отрицательными числами. Если орграф не содержит контуров с отрицательным весом, достижимых из вершины  S , то вес кратчайшего пути от  S до каждой вершины  v Î V остается определенной величиной, даже если он принимает отрицательное значение.

Если же такой контур достижим из истока  S , веса кратчайших путей перестают быть определенными величинами. Ни один путь из вершины S в любую из вершин контура не может быть кратчайшим, так как всегда можно найти путь с меньшим весом, который проходит по предложенному «кратчайшему» пути, а потом обходит контур с отрицательным весом.

Если на пути от S  к  v  встречается контур с отрицательным весом, то его вес определяют равным  «– ∞».

В некоторых алгоритмах поиска кратчайшего пути предполагается, что веса всех дуг положительны (алгоритм Дейкстры), в других – дуги могут иметь отрицательные веса (алгоритм Форда-Беллмана и Флойда-Уоршелла). В случае дуг с отрицательными весами алгоритмы выявляют наличие контуров с отрицательным весом (если они есть), и если такие контуры недостижимы из истока, то алгоритмы дают конкретные кратчайшие пути.

Ни один из кратчайших путей не может содержать контуров, как с отрицательным, так и с положительным весом.

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

Представление  кратчайших  путей, релаксация  (ослабление).

Важно знать не только вес кратчайшего пути, но и последовательность вершин, по которым проходит этот путь . Для этого в заданном графе  G  для каждой вершины  v  поддерживается метка – предшественник  Θ[v], в роли которого выступает либо другая вершина, либо значение  niℓ (0).

В алгоритмах поиска кратчайших путей метки Θ присваиваются таким образом, что цепочка предшественников, которая начинается в вершине v, позволяет проследить путь, обратный кратчайшему пути из вершины S в вершину v.

Кратчайший путь из истока S в вершину v представляет собой дерево с корнем  S. Дерево кратчайших путей – содержит кратчайший путь из  S к каждой вершине, достижимой из  S.

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

На рис. 1 в каждой вершине указан вес кратчайшего пути от  S  к этой вершине. На рис. 2 представлены два разных дерева кратчайших путей (жирно выделены)

Ослабление (релаксация).

В алгоритмах поиска кратчайших путей используется метод ослабления или релаксации. Для каждой вершины  v Î V  поддерживается метка  d[v], представляющая собой верхнюю границу веса, которым обладает кратчайший путь из вершины S в вершину v; d[v] – это оценка кратчайшего пути.

В начале алгоритма проводится инициализация (установка начальных значений) оценок кратчайших путей и предшественников.

Инициализация

1. d[S] : = 0

2. Для каждой из остальных вершин v полагаем

d[v] = ¥,   Θ[v] = niℓ.

Процесс ослабления дуги (u, v) заключается в проверке, нельзя ли улучшить найденный до сих пор кратчайший путь к вершине v, проведя его через вершину u, а также в обновлении меток d[v], Θ[v] при наличии такой возможности улучшения. Ослабление может уменьшить оценку кратчайшего пути d[v] и обновить метку Θ[v] вершины v.

Проводится ослабление так:

1. Если  d[v] > d[u] + c(u, v), то

заменить d[v] на d[u] + c(u, v)

и метка Θ[v] = u;

2. Если  d[v] = d[u] + c(u, v), то

метка d[v] не меняется, добав-

ляется метка Θ[v] = u;

3. Если  d[v] < d[u] + c(u, v), то

метки d[v], Θ[v] не меняются.

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

В рассмотренном ниже алгоритме Форда-Беллмана сначала проводится инициализация, затем производится ослабление дуг.

АЛГОРИТМ ФОРДА-БЕЛЛМАНА

Алгоритм Форда-Беллмана позволяет решать задачу о кратчайшем пути из одной вершины в общем случае, когда веса дуг могут быть отрицательными. Он основан на метках вершин, причем в конце k-й итерации метки равны дли­нам тех кратчайших путей, которые содержат не более к + 1 дуг. В течение всего процесса работы алгоритма никакая метка не рассматривается как окон­чательная.

К его достоинствам относится то, что он определяет, содержится или нет в графе контур с отрицатель­ным весом, достижимый из вершины s.

Орграф G хранится в виде списков смежности вершин. Вместе с каждой дугой хранится и ее вес.

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

Обозначим: d(k)(Vi) - метка вершины Vi в конце (к + 1)-й итерации, она оз­начает длину кратчайшего пути, состоящего из к дуг;

θ(k)(Vi) - эта метка указывает вершину, непосредственно предшествую­щую вершине Vi в кратчайшем пути от s к Vi во время k-й итерации.

Обе метки хранятся вместе с каждой вершиной во время вычислений.

Если начальной берется вершина s, то для всех Vi Є Гs полагают θ1(vi) = s, а для остальных вершин берут произвольно, например, θ1 = 0.

Алгоритм Форда-Беллмана

1. Инициализация.

Положить s = Vi, k=l, d(1)(s) = 0, d(1)(Vi) = c(s, Vi) для всех Vi Гs и d(1)(Vi) = ∞ для остальных Vi; положить S = Гs.

2. Обновление меток.

Для каждой вершины Vi Гs вычислить

,                            (1)

где Тi = Г-1 Vi ∩ S (S содержит теперь все вершины, для которых крат­чайшие пути из s состоят из к дуг)

(множество Тi содержит те вершины, для которых кратчайшие текущие пути из S состоят из k дуг, т.е. те вершины, лежащие в S и для которых существуют дуги к Vi). Для вершин Vi Г(S) положить d(k+1)(Vi)= d(k)(Vi) (метка d не меняется).

3. Проверка на окончание.

Если  k < n - 1   и  d(k+1)(Vi )= d(k)(Vi) для всех Vi, то получаем оконча­тельный ответ, метки равны весам кратчайших путей. Останов.

Если k < n - 1 и d(k+1)(Vi )≠d(k)(Vi) для некоторой вершины Vi, то пере­ход на 4.

Если k = n - 1 и d(k+1)(Vi )≠d(k)(Vi) для некоторой вершины Vi, то в орграфе существует контур отрицательного веса и задача не имеет реше­ния. Останов.

4. Обновить множество S, внеся в него вершины Vi

(S содержит теперь все вершины, кратчайшие пути до которых из   s имеют длину к + 1)

5. Положить k: = k + 1 и перейти к 2.

Метки θ(k)(Vi) меняются в соответствии с (1), а именно, θ(k+1)(Vi)= θ(k)(Vi) (метка не меняется), если в (1) в квадратных скобках наименьшим будет первый член, и θ(k+1)(Vi)= Vj, если наименьшим будет второй член.

Если θ(Vi) – вектор, состоящий из меток θ при завершении работы алгоритмы, то кратчайший путь от s к Vi получается в обратном порядке: s, ..., θ3(Vi), θ2(Vi), θ(Vi), Vi,где θ2(Vi) – это сокращение для θ(θ(Vi)) и т.д.

Алгоритм Форда-Беллмана  базируется на принципе динамического программирования и на том факте, что если не существует никакого кратчайшего пути из к дуг, то не может существовать также и никакой кратчайший путь из k + 1 дуг.

Перечень используемых величин (константы, переменные, массивы) и их назначение.

В программе используются следующие переменные:

1.      maxver – количество вершин орграфа;

2.      Ves – матрица веов дуг;

3.      Ras – матрица расстояний;

4.      S – начальная вершина;

5.      T – конечная вершина;

Входная и выходная информация, диапазон изменения величин.

1.                       Входная информация:

1.1.                      Количество вершин maxver – целые числа от 4 до 50;

1.2.                      Элементы матрицы весов Ves – целые числа от -100 до 100;

1.3.                      Начальная вершина S – целые числа от 1 и до введенного количества вершин (максимум – 50);

1.4.                      Конечная вершина T – целые числа от 1 и до введенного количества вершин

2.                       Выходная информация:

2.1.                      Матрица весов графа.

2.2.                      Матрица расстояний от начальной вершины до всех остальных;

2.3.                      Кратчайший путь от начальной вершины до конечной вершины.

БЛОК-СХЕМА АЛГОРИТМА.

ЗАКЛЮЧЕНИЕ.

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

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ.

1.                 Павловская  Т.А.. С/С++  Программирование на языке высокого уровня. СПб: Питер, 2006.

2.                 Хусаинов Б.С.. Структуры и алгоритмы обработки данных. Примеры на языке Си. М: Финансы и статистика, 2004.

3.                 Подбельский В.В.. Язык Си++. М: Финансы и статистика, 2003.

ПРИЛОЖЕНИЕ A.

Инструкция к использованию программы.

1. Ввод команд.

После запуска программа выдаст вам сообщение об вводе команды. Всего команд две: “open” и “vvod”. Ваша задачи вести одну из них и нажать клавишу “Enter”.