Графы алгоритм дейкстры реферат

Обновлено: 04.07.2024

Работа содержит 1 файл

Алгоритм Дейкстры.docx

Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами s и t при положительных длинах дуг. Этот алгоритм,. предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи.
Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны m вершин, ближайших к вершине s (близость любой вершины x к вершине s определяется длиной кратчайшего пути, ведущего из s в x). Пусть также известны сами кратчайшие пути, соединяющие вершину s с выделенными m вершинами). Покажем теперь, как может быть определена (m + 1)-я ближайшая к s вершина.
Окрасим вершину s и m ближайших к ней вершин. Построим для каждой неокрашенной вершины y пути, непосредственно соединяющие с помощью дуг (х, у) каждую окрашенную вершину х с у. Выберем из этих путей кратчайший, и будем считать его условно кратчайшим путем из вершины s в вершину y.
Какая же из неокрашенных вершин является (m + 1)-й ближайшей к s вершиной? Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины s в (m +1)-ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т. е. вершины, входящие в число m вершин, ближайших к вершине s.
Итак, если известны m ближайших к s вершин, то (m + 1)-я ближайшая к s вершина может быть найдена так, как это описано выше. Начиная с m = 0, описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины s к вершине t.
Имея в виду приведенные соображения, мы можем теперь формально описать алгоритм Дейкстры.

Каждой вершине X в ходе алгоритма присваивается число d(x), равное длине кратчайшего пути из вершины S в вершину X и включающем только окрашенные вершины. Положить d(s)=0 и d(x)=∞ для всех остальных вершин графа. Окрашиваем вершину S и полагаем y=S, где y – последняя окрашенная вершина.
Для каждой неокрашенной вершины X пересчитывается величина d(x) по следующей формуле:

Каждый раз окрашивается вершина и дуга, заходящая в эту вершину. Окрашенные дуги не могут образовывать цикл, а образуют в исходном графе дерево с корнем (началом) в вершине s. Это дерево называют ориентированным деревом кратчайших путей. Путь из s в t принадлежит этому дереву. При поиске одного кратчайшего пути процедура наращивания завершается при достижении конечной вершины этого пути. Нам же необходимо получить все кратчайшие пути начинающиеся в вершине №1. Для этого процедуру наращивания ориентированного дерева продолжается до тех пор, пока все вершины не будут включены. Таким образом, мы получаем ориентированное дерево кратчайших путей, которое является покрывающим деревом графа.
Иногда в графе имеются несколько кратчайших путей. Кратчайший путь будет единственным, если в алгоритме ни разу не возникает неоднозначность при окрашивании дуги.

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

ГОСТ

Основная идея алгоритма Дейкстры

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

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

Кратчайший путь между вершинами – это путь минимально возможной длины, соединяющий на графе одну вершину с другой.

Длина пути – это сумма длин всех дуг (ориентированных рёбер – рёбер с чётко указанными началом и концом), по которым проходит этот путь.

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

Алгоритм Дейкстры применяется исключительно для графов с неотрицательными длинами дуг.

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

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

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

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

Готовые работы на аналогичную тему

Пример поиска кратчайшего пути по алгоритму

Рассмотрим применение алгоритма Дейкстры к конкретному примеру. Пусть задан граф, представленный на рисунке:

Рисунок 1. Граф. Автор24 — интернет-биржа студенческих работ

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

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

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

Каждый раз длина пути пересчитывается по формуле:

$r(x,y)$ – вес дуги, соединяющей вершины $x$ и $y$,
$S(y)$ – длина пути, соединяющего начальную точку $s$ с вершиной $y$.

Применим теперь данный алгоритм к графу, изображённому на рисунке.

Поскольку, очевидно, $S(s) = 0$ – самое короткое расстояние на графе (от стартовой точки $s$ до неё же), то отмечаем вершину $s$. При этом изначально считается, что $S(y) = ∞$ для всех остальных (отличных от $s$) вершин заданного графа.

Согласно алгоритму полагаем, что $x = s$. И далее вычисляем величины $S(y)$ для всех непомеченных вершин графа:

Выбираем среди полученных величин минимальную. В данном случае это $S(c) = 2$. Поэтому отмечаем вершину $c$ и закрашиваем дугу $(s,c)$, которая соответствует кратчайшему пути с длиной $S(c)$.

Продолжаем далее, пока не пройдём по графу до конечного пункта – вершины $t$. Сейчас оказалось, что $x = c$. И теперь по формуле пересчитываем величины $S(y)$ для ещё не отмеченных вершин:

Так как величина $S(a) = 5$ является минимальной из всех полученных на этом шаге величин, то отмечаем вершину $a$ и закрашиваем на графе дугу $(s,a)$, которая и определяет величину $S(a)$.

Аналогично предыдущему шагу за точку $x$ принимаем только что помеченную точку: $x = a$. Снова пересчитываем величины $S(y)$ для оставшихся вершин:

Поскольку величина $S(d) = 6$ оказалась здесь наименьшей, то отмечаем вершину $d$ и закрашиваем дугу $(c,d)$, определяющую эту величину $S(d)$.

Получили, что $x = d$. Теперь по формуле вычисляем величины:

Так как величина $S(b) = 7$ меньше величины $S(t)$, то на этом шаге помечаем вершину $b$ и закрашиваем дугу $(c,b)$, соответствующую выбранному кратчайшему расстоянию.

И теперь последняя итерация алгоритма. Здесь $x = b$ и расстояние

Наконец, вершина $t$ достигнута. Отмечаем её и закрашиваем кратчайший путь, ведущий к ней на этом шаге – дугу $(d,t)$.

В итоге, после применения алгоритма Дейкстры, мы получили дерево кратчайших путей, состоящее из дуг $(s,c), (s,a), (c,d), (c,b)$ и $(d,t)$:

Рисунок 2. Дерево кратчайших путей. Автор24 — интернет-биржа студенческих работ

Из них единственный кратчайший путь, соединяющий вершину $s$ с вершиной $t$, проходит по дугам $(s,c), (c,d), (d,t)$ и имеет длину $2 + 4 + 2 = 8$.

Пошаговое описание алгоритма Дейкстры

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

Перечислим шаги алгоритма Дейкстры по пунктам:

На графе каждой вершине $y$ ставится в соответствие число $S(y)$, которое вычисляется как длина условно кратчайшего пути из начальной точки $s$ в вершину $y$. При этом рассматриваются только пути, проходящие через уже помеченные вершины. Изначально полагается, что $S(s) = 0$ и $S(y) = ∞$ для любой (отличной от $s$) вершины $y$. Отмечается вершина $s$, и поэтому переменная $x = s$.
Для каждой неотмеченной вершины $y$ заданного графа пересчитывается величина $S(y)$ по следующей формуле: $S(y) = min\$, где $x$ – промежуточная вершина, отмеченная на предыдущем шаге. Данная формула позволяет выбрать наиболее короткий путь от начальной точки графа до нужной вершины, сравнивая величину пути $S(y)$ с длиной пути, составленного из нескольких дуг и включающего при этом помеченную вершину $x$.

Далее возможны следующие варианты:

Если $S(y) = ∞$ для всех неотмеченных вершин $y$, то отсутствуют пути из $s$ в оставшиеся вершины графа и требуется закончить процедуру алгоритма.
Иначе пометить на графе ту вершину $y$, для которой величина $S(y)$ оказалась минимальной, а также закрасить дугу, оптимально приводящую в эту вершину $y$. Далее полагаем, что $x = y$.

Если оказалось, что $x = t$, то алгоритм завершён, и в результате его применения найден искомый кратчайший путь (это единственный путь из вершины $s$ в вершину $t$, который в ходе выполнения алгоритма получился на графе закрашенным). Иначе требуется перейти к пункту 2 алгоритма и снова повторять его действия до тех пор, пока не будет получен кратчайший путь, соединяющий вершины $s$ и $t$.

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

Обобщение алгоритма Дейкстры на случай, когда некоторым из его дуг соответствуют отрицательные весовые коэффициенты, получило название алгоритма Беллмана-Форда.

Настоящая курсовая работа моделирует логическую задачу, состоящую из следующих частей:

1) Изучение конкретного раздела дискретной математики.

2) Решение 5-ти задач по изученной теме с методическим описанием.

3) Разработка и реализация в виде программы алгоритма по изученной теме. Разработка программного интерфейса.

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

дискретный математика программа интерфейс

Пусть дан граф G=(X, Г), дугам которого приписаны веса (стоимости), задаваемые матрицей C=[cij]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины sX до заданной конечной вершины tX, при условии, что такой путь существует, т.е. при условии tR(s). Здесь R(s) – множество, достижимое из вершины s. Элементы cij матрицы весов C могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в G не было циклов с отрицательным суммарным весом. Если такой цикл Ф все же существует и xi – некоторая его вершина, то, двигаясь от s к xi, обходя затем Ф достаточно большое число раз и попадая наконец в t, мы получим путь со сколь угодно малым () весом. Таким образом, в этом случае кратчайшего пути не существует.

Если, с другой стороны, такие циклы существуют, но исключаются из рассмотрения, то нахождение кратчайшего пути (простой цепи) между s и t эквивалентно нахождению в этом графе кратчайшего гамильтонова пути с концевыми вершинами s и t. Это можно усмотреть из следующего факта. Если из каждого элемента cij матрицы весов C вычесть достаточно большое число L, то получится новая матрица весов C'=[cij'], все элементы cij' которой отрицательны. Тогда кратчайший путь от s к t – с исключением отрицательных циклов – необходимо будет гамильтоновым, т.е. проходящим через все другие вершины. Так как вес любого гамильтонова пути с матрицей весов C' равен весу этого пути с матрицей весов C, но уменьшенному на постоянную величину (n-1)ЧL, то кратчайший путь (простая цепь) от s к t с матрицей C' будет кратчайшим гамильтоновым путем от s к t при первоначальной матрице C. Задача о нахождении кратчайшего гамильтонова пути намного сложнее, чем задача о кратчайшем пути. Поэтому мы будем предполагать, что все циклы в G имеют неотрицательный суммарный вес. Отсюда также вытекает, что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.

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

1) Для заданной начальной вершины s найти кратчайшие пути между t и всеми другими вершинами xiX.

2) Найти кратчайшие пути между всеми парами вершин.

Частные случаи, когда все cij неотрицательны, встречаются на практике довольно часто (например, когда cij являются расстояниями), так что рассмотрение этих специальных алгоритмов оправдано. Мы будем предполагать, что матрица не удовлетворяет, вообще говоря, условию треугольника, т.е. не обязательно для всех . В противном случае кратчайший путь между xj и xj состоит из одной единственной (xj xj) дуги, если такая дуга существует, и задача становится тривиальной. Если в графе G дуга (xj xj) отсутствует, то ее вес полагается равным .

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

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

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

Пусть l(xi) – пометка вершины xi.

Присвоение начальных значений

Шаг 1. Положить и считать эту пометку постоянной. Положить для всех xis и считать эти пометки временными. Положить p=s.

Шаг 2. Для всех , пометки которых временные, изменить пометки в соответствии со следующим выражением: .

Превращение пометки в постоянную

Шаг 3. Среди всех вершин с временными пометками найти такую, для которой .

Шаг 4. Считать пометку вершины xi* постоянной и положить p= xi*.

Шаг 5. (1) (Если надо найти лишь путь от s к t.)

Если p=t, то l(p) является длиной кратчайшего пути. Останов.

Если pt, перейти к шагу 2.

(Если требуется найти пути от s ко всем остальным вершинам.)

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

Если некоторые пометки являются временными, перейти к шагу 2.

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

Допустим, что на некотором этапе постоянные пометки дают длины кратчайших путей. Пусть S1 – множество вершин с этими пометками, а S2 – множество вершин с временными пометками. В конце шага 2 каждой итерации временная пометка l(xi) дает кратчайший путь от s к xi, проходящий полностью по вершинам множества S1. (Так как при каждой итерации во множество S1 включается только одна вершина, то обновление пометки l(xi) требует только одного сравнения на шаге 2.)

Пусть кратчайший путь от s к xi* не проходит целиком по S1 и содержит по крайней мере одну вершину из S2, и пусть xjS2 – первая такая вершина в этом пути. Так как по предположению cij неотрицательны, то часть пути от xj к xi* должна иметь неотрицательный вес и. Это, однако, противоречит утверждению, что l(xi*) – наименьшая временная пометка, и, следовательно, кратчайший путь к xi* проходит полностью по вершинам множества S1, и поэтому l(xi*) является его длиной.

Так как вначале множество S1 равно (s) при каждой итерации к S1 добавляется xi*, то предположение, что l(xi*) равно длине кратчайшего пути xiS1, выполняется при каждой итерации. Отсюда по индукции следует, что алгоритм дает оптимальный ответ.

Если требуется найти кратчайшие пути между s и всеми другими вершинами полного связного графа с n вершинами, то в процессе работы алгоритма выполняются операций сложения и сравнения на шаге 2 и еще операций сравнения на шаге 3. Кроме того, при осуществлении шагов 2 и 3 необходимо определить, какие вершины временные, а для этого нужно еще операций сравнения. Эти величины являются верхними границами для числа операций, необходимых при отыскании кратчайшего пути между заданными вершинами s и t. Они действительно достигаются, если окажется, что вершина t будет последней вершиной, получившей постоянную пометку.

Как только длины кратчайших путей от s будут найдены (они будут заключительными значениями пометок вершин), сами пути можно получить при помощи рекурсивной процедуры с использованием соотношения (*). Так как вершина xi' непосредственно предшествует вершине xi в кратчайшем пути от s к xi, то для любой вершины xi соответствующую вершину xi' можно найти как одну из оставшихся вершин, для которой

2.2 Задачи с методическим описанием

Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа

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

Алгоритм работает так:

Шаг 2. - все пометки временные.

Шаг 3. соответствует x7.

Шаг 4. x7 получает постоянную пометку l(x7)=3+, p=x7.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - все пометки временные.

Шаг 3. соответствует x2.

Шаг 4. x2 получает постоянную пометку l(x2)=5+, p=x2.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - только вершины x3 и x9 имеют временные пометки.

Шаг 3. соответствует x8.

Шаг 4. x8 получает постоянную пометку l(x8)=6+, p=x8.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - только вершины x5, x6 и x9 имеют временные пометки.

Шаг 3. соответствует x4.

Шаг 4. x4 получает постоянную пометку l(x4)=7+, p=x4.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - только вершины x5, x6 и x3 имеют временные пометки.

Шаг 3. соответствует x9.

Шаг 4. x9 получает постоянную пометку l(x9)=11+, p=x9.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - только вершина x6 имеет временную пометку.

Шаг 3. соответствует x5.

Шаг 4. x5 получает постоянную пометку l(x5)=12+, p=x5.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - только вершина x6 имеет временную пометку.

Шаг 3. соответствует x6.

Шаг 4. x6 получает постоянную пометку l(x5)=17+, p=x6.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - только вершина x3 имеет временную пометку.

Шаг 3. x3 получает постоянную пометку l(x3)=23+.

Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа

Алгоритм работает так:

Шаг 2. - все пометки временные.

Шаг 3. соответствует x5.

Шаг 4. x5 получает постоянную пометку l(x5)=2+, p=x5.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - все пометки временные.

Шаг 3. соответствует x2.

Шаг 4. x2 получает постоянную пометку l(x2)=3+, p=x2.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - только вершины x3 и x4 имеют временные пометки.

Шаг 3. соответствует x3.

Шаг 4. x3 получает постоянную пометку l(x3)=8+, p=x3.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - все пометки временные.

Шаг 3. соответствует x4.

Шаг 4. x4 получает постоянную пометку l(x4)=9+, p=x4.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - только вершины x7, x6 и x9 имеют временные пометки.

Шаг 3. соответствует x7.

Шаг 4. x7 получает постоянную пометку l(x7)=13+, p=x7.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - только вершины x6 и x8 имеют временные пометки.

Шаг 3. соответствует x9.

Шаг 4. x9 получает постоянную пометку l(x9)=20+, p=x9.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - только вершина x6 имеет временную пометку.

Шаг 3. соответствует x6.

Шаг 4. x6 получает постоянную пометку l(x6)=17+, p=x6.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. временных пометок нет.

Шаг 3. x8 получает постоянную пометку l(x8)=29+.

Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа.

дискретный математика программа интерфейс

Алгоритм работает так:

Шаг 2. - все пометки временные.

Шаг 3. соответствует x4.

Шаг 4. x4 получает постоянную пометку l(x4)=7+, p=x4.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 2. - все пометки временные.

Шаг 3. соответствует x2.

Шаг 4. x2 получает постоянную пометку l(x2)=9+, p=x2.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 3. соответствует x7.

Шаг 4. x7 получает постоянную пометку l(x7)=11+, p=x7.

Шаг 5. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2.

Шаг 3. соответствует x8.

Шаг 4. x8 получает постоянную пометку l(x8)=14+, p=x8.

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

Алгоритм Дейкстры ( реферат , курсовая , диплом , контрольная )

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

Настоящая курсовая работа моделирует логическую задачу, состоящую из следующих частей:

1) Изучение конкретного раздела дискретной математики.

2) Решение 5-ти задач по изученной теме с методическим описанием.

3) Разработка и реализация в виде программы алгоритма по изученной теме. Разработка программного интерфейса.

2. Введение

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

дискретный математика программа интерфейс Пусть дан граф G=(X, Г), дугам которого приписаны веса (стоимости), задаваемые матрицей C=[c_ij]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины sX до заданной конечной вершины tX, при условии, что такой путь существует, т. е. при условии tR (s). Здесь R (s) — множество, достижимое из вершины s. Элементы c_ij матрицы весов C могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в G не было циклов с отрицательным суммарным весом. Если такой цикл Ф все же существует и x_i — некоторая его вершина, то, двигаясь от s к x_i, обходя затем Ф достаточно большое число раз и попадая наконец в t, мы получим путь со сколь угодно малым () весом. Таким образом, в этом случае кратчайшего пути не существует.

Если, с другой стороны, такие циклы существуют, но исключаются из рассмотрения, то нахождение кратчайшего пути (простой цепи) между s и t эквивалентно нахождению в этом графе кратчайшего гамильтонова пути с концевыми вершинами s и t. Это можно усмотреть из следующего факта. Если из каждого элемента c_ij матрицы весов C вычесть достаточно большое число L, то получится новая матрица весов C'=[c_ij'], все элементы c_ij' которой отрицательны. Тогда кратчайший путь от s к t — с исключением отрицательных циклов — необходимо будет гамильтоновым, т. е. проходящим через все другие вершины. Так как вес любого гамильтонова пути с матрицей весов C' равен весу этого пути с матрицей весов C, но уменьшенному на постоянную величину (n-1)?L, то кратчайший путь (простая цепь) от s к t с матрицей C' будет кратчайшим гамильтоновым путем от s к t при первоначальной матрице C. Задача о нахождении кратчайшего гамильтонова пути намного сложнее, чем задача о кратчайшем пути. Поэтому мы будем предполагать, что все циклы в G имеют неотрицательный суммарный вес. Отсюда также вытекает, что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.

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

1) Для заданной начальной вершины s найти кратчайшие пути между t и всеми другими вершинами x_iX.

2) Найти кратчайшие пути между всеми парами вершин.

Частные случаи, когда все c_ij неотрицательны, встречаются на практике довольно часто (например, когда c_ij являются расстояниями), так что рассмотрение этих специальных алгоритмов оправдано. Мы будем предполагать, что матрица не удовлетворяет, вообще говоря, условию треугольника, т. е. не обязательно для всех. В противном случае кратчайший путь между x_j и x_j состоит из одной единственной (x_j x_j) дуги, если такая дуга существует, и задача становится тривиальной. Если в графе G дуга (x_j x_j) отсутствует, то ее вес полагается равным .

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

Пусть l (x_i) — пометка вершины x_i.

Присвоение начальных значений

Шаг 1. Положить и считать эту пометку постоянной. Положить для всех x_is и считать эти пометки временными. Положить p=s.

Шаг 2. Для всех, пометки которых временные, изменить пометки в соответствии со следующим выражением: .

Превращение пометки в постоянную

Шаг 3. Среди всех вершин с временными пометками найти такую, для которой .

Шаг 4. Считать пометку вершины x_i* постоянной и положить p= x_i*.

Если p=t, то l (p) является длиной кратчайшего пути. Останов.

Если pt, перейти к шагу 2.

(Если требуется найти пути от s ко всем остальным вершинам.)

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

Если некоторые пометки являются временными, перейти к шагу 2.

Допустим, что на некотором этапе постоянные пометки дают длины кратчайших путей. Пусть S₁ — множество вершин с этими пометками, а S₂ — множество вершин с временными пометками. В конце шага 2 каждой итерации временная пометка l (x_i) дает кратчайший путь от s к x_i, проходящий полностью по вершинам множества S₁. (Так как при каждой итерации во множество S₁ включается только одна вершина, то обновление пометки l (x_i) требует только одного сравнения на шаге 2.)

Пусть кратчайший путь от s к x_i* не проходит целиком по S₁ и содержит по крайней мере одну вершину из S₂, и пусть x_jS₂ — первая такая вершина в этом пути. Так как по предположению c_ij неотрицательны, то часть пути от x_j к x_i* должна иметь неотрицательный вес и. Это, однако, противоречит утверждению, что l (x_i*) — наименьшая временная пометка, и, следовательно, кратчайший путь к x_i* проходит полностью по вершинам множества S₁, и поэтому l (x_i*) является его длиной.

Так как вначале множество S₁ равно (s) при каждой итерации к S₁ добавляется x_i*, то предположение, что l (x_i*) равно длине кратчайшего пути x_iS₁, выполняется при каждой итерации. Отсюда по индукции следует, что алгоритм дает оптимальный ответ.

Как только длины кратчайших путей от s будут найдены (они будут заключительными значениями пометок вершин), сами пути можно получить при помощи рекурсивной процедуры с использованием соотношения (*). Так как вершина x_i' непосредственно предшествует вершине x_i в кратчайшем пути от s к x_i, то для любой вершины x_i соответствующую вершину x_i' можно найти как одну из оставшихся вершин, для которой

2.2 Задачи с методическим описанием

Найти кратчайшие пути от вершины 1 ко всем другим вершинам графа

Читайте также: