nter">  - длина ребра

 

Алгоритм  Флойда - Уоршелла последовательно вычисляет все значения , для k от 1 до n. Полученные значения являются длинами кратчайших путей между вершинами .

Сложность алгоритма

     Три вложенных цикла содержат операцию, исполняемую за константное время.  

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

     Алгоритм Беллмана - Форда - алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана - Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом (Bellman) и Лестером Фордом (Ford).

Решение задачи алгоритмом Беллмана - Форда  на графе без отрицательных циклов.

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

     Для нахождения кратчайших путей от одной  вершины до всех остальных, воспользуемся  методом динамического программирования. Построим матрицу Aij, элементы которой  будут обозначать следующее: Aij - это длина кратчайшего пути из s в i, содержащего не более j рёбер.

     Путь, содержащий 0 рёбер, существует только до вершины s. Таким образом, Ai0 равно 0 при i = s, и  в противном случае.

     Теперь  рассмотрим все пути из s в i, содержащие ровно j рёбер. Каждый такой путь есть путь из j − 1 ребра, к которому добавлено  последнее ребро. Если про пути длины j − 1 все данные уже подсчитаны, то определить j-й столбец матрицы  не составляет труда.

Граф  с отрицательными циклами

Алгоритм  Беллмана - Форда позволяет очень просто определить, существует ли в графе G отрицательный цикл, достижимый из вершины s. Достаточно произвести внешнюю итерацию цикла не |V| - 1, a ровно |V| раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины строго уменьшилась, то в графе есть отрицательный цикл, достижимый из s. На основе этого можно предложить следующую оптимизацию. Можно отслеживать изменения в графе и, как только они закончатся, дальнейшие итерации будут бессмысленны. Значит можно сделать выход из цикла.

Сложность алгоритма O(V * E), V - кол-во вершин, E - кол-во ребер (Количественно-зависимый по трудоемкости алгоритм).

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

Алгоритм

Описание

     В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U - массив булевых переменных.

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

     На  каждом шаге цикла мы ищем вершину  с минимальным расстоянием и  флагом равным нулю. Затем мы устанавливаем  в ней флаг в 1 и проверяем все  соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 . Последний случай возможен тогда и только тогда, когда граф G не связан.

Доказательство  корректности

     Пусть l(v) - длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z). 
База. Первой посещается вершина a. В этот момент d(a)=l(a)=0. 
Шаг. Пускай мы выбрали для посещения вершину . Докажем, что в этот момент d(z)=l(z). Для начала отметим, что для любой вершины v, всегда выполняется (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P - кратчайший путь из a в z, y - первая непосещённая вершина на P, x - предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть, ведущая из a через x в y, тоже кратчайшая, следовательно l(y)=l(x)+w(xy). По предположению индукции, в момент посещения вершины x выполнялось d(x)=l(x), следовательно, вершина y тогда получила метку не больше чем d(x)+w(xy)=l(x)+w(xy)=l(y). Следовательно, d(y)=l(y). С другой стороны, поскольку сейчас мы выбрали вершину z, её метка минимальна среди непосещённых, то есть . Комбинируя это с , имеем d(z)=l(z), что и требовалось доказать.

Поскольку алгоритм заканчивает работу, когда  все вершины посещены, в этот момент d=l для всех вершин.[3]

 

3.Решение задачи «вручную»

     Каждой  вершине из V сопоставим метку - минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

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

     Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.[5]

     Пример

     Рассмотрим  выполнение алгоритма на примере  графа, показанного на рисунке. Пусть  требуется найти расстояния от 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 - вершина 3, так имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

      
 Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояние до 2-ой вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22< , устанавливаем метку вершины 4 равной 22.

 

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Третий  шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Дальнейшие  шаги. Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

     Завершение  выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.

4.Программа «Определение кратчайшего пути в графе»

 

     Программа написана на языке С# версии 2.0 в среде Microsoft Visual Studio 2005 и в ниже представленном листинге выполняет пример, приведенный выше. Отладка производилась в операционной системе MS Windows ХР на компьютере совместимом с IBM PC с процессором Pentium.

Листинг программы:

 

6.ЗАКЛЮЧЕНИЕ

       Теория графов находит широкое применение в различных областях науки и техники:

Графы и информация

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

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

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

Графы и химия

       Еще А. Кэли рассмотрел задачу о возможных  структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:

       C_nH_2n+2

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

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