Алгоритм Дейкстры (стр. 1 из 4)

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

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

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

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

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

2. Введение

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

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

Пусть дан граф G=(X, Г), дугам которого приписаны веса (стоимости), задаваемые матрицей C=[c_ij]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s

X до заданной конечной вершины t X, при условии, что такой путь существует, т.е. при условии t R(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_i

X.

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

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

для всех

. В противном случае кратчайший путь между x_j и x_j состоит из одной единственной (x_jx_j) дуги, если такая дуга существует, и задача становится тривиальной. Если в графе G дуга (x_jx_j) отсутствует, то ее вес полагается равным

.

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

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

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

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

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

)

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

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

Шаг 1. Положить

и считать эту пометку постоянной. Положить для всех xi

s и считать эти пометки временными. Положить p=s.

Обновление пометок

Шаг 2. Для всех

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

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

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

.

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

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

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

Если p

t, перейти к шагу 2.

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

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

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

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

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

Пусть кратчайший путь от s к x_i* не проходит целиком по S₁ и содержит по крайней мере одну вершину из S₂, и пусть x_j

S₂ – первая такая вершина в этом пути. Так как по предположению c_ij неотрицательны, то часть пути от x_j к x_i* должна иметь неотрицательный вес

и . Это, однако, противоречит утверждению, что l(x_i*) – наименьшая временная пометка, и, следовательно, кратчайший путь к x_i* проходит полностью по вершинам множества S₁, и поэтому l(x_i*) является его длиной.

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

xi

S₁, выполняется при каждой итерации. Отсюда по индукции следует, что алгоритм дает оптимальный ответ.

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

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