Читать курсовая по математике: "Алгоритм Дейкстры" Страница 2

(Назад) (Cкачать работу)

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

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

Наиболее эффективный алгоритм решения задачи о кратчайшем (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 и содержит по крайней мере одну

Похожие работы