1-й сем-ДМ-слайды-ДГТУ / Графы-3,4 лекции / Кратчайшие пути в графе

Кратчайшие пути в графе.

Пусть дан граф G = (x,Г), дугам которого приписаны веса (стоимости), задаваемые матрицей С = [C_{i j}]. Задачей о кратчайшем пути от заданной начальной вершины Sx до заданной конечной вершины tx, при условии, что такой путь существует, то есть при условии tR (S). R(S) –множество, достижимое из вершины S. Элементы C_{i j} матрицы С могут быть > 0, <0, = 0. Единственное ограничение в G нет циклов с отрицательным суммарным весом. Таким образом, в этом случае кратчайшего пути не существует. Если такие циклы существуют, но исключаются из рассмотрения, что нахождение кратчайшего пути (простой цепи) между S и t эквивалентно нахождению в этом графе кратчайшего гамильтонова пути с концевыми вершинами S и t. Это видно из следующего факта. Если из каждого C_i,j матрицы весов С вычесть достаточно большое число L, то получится новая матрица вес ов с^’ = [C_i,j’], все элементы которой C_i,j’ – отрицательны. Тогда кратчайший путь от S к t с отрицательных циклов – необходимо будет гамильтоновым, то есть проходящим через все другие вершины. Так как вес любого гамильтонова пути с матрицей весов С^’ равен весу этого пути с матрицей С, но уменьшенному на постоянную величину (n-1) α, то кратчайший путь (простая цепь) от S к t с матрицей С^’ будет кратчайшим гамильтоновым путем при первоначальной матрице. Задача нахождения кратчайшего гамильтонова пути намного сложнее, чем задача о кратчайшем пути. Поэтому будем предлагать., что все циклы в G прямой неотрицательный суммарный вес. Отсюда следует, что неориентированные дуги (ребра) графа G не могут иметь отрицательного веса. Возникают следующие задачи:

1) Для заданной вершины S найти кратчайшие пути между S и всеми другими вершинами x_i x.

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

Матрица весов не удовлетворяет условию треугольников, то есть не обязательно C_{i j}

С_{i k} + C_{k j} для всех i, j, k. В противном случае кратчайший путь между x_i и x_j состоит из одной единственной дуги (если она существует) и задача становится тривиальной. На практике требуется найти не только кратчайший путь, но второй, третий и т. д. под кратчайшие пути. Можно учитывать способности и надежности дуги.

Кратчайший путь между двумя заданными вершинами Sи t.

Рассмотрим случай C_{i j} 0. Алгоритм Дейкстры. Он основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от S к этой вершине. Эти пометки (их величины) постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Это указывает на то, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от S к рассматриваемой вершине. Пусть l (x_i) – пометка вершины x_i. Присвоение начальных значений.

Шаг 1. Положить l (S) = 0 и считать эту пометку постоянной. Положите l (x_i) = для всех x_i S и считать эти пометки временными. Положить р = S. Обновление пометок.

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

l (x_i) min [l(x_i), l(p) + c (p, x_i)]

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

Шаг 3. Среди всех вершин с временными пометками, найти такую, для которой l (x_i^*) = min [l(x_i)].

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

Шаг 5.

а). Если нужно найти лишь путь от S к t. Если р = t, то l(p) – длина кратчайшего пути. Если рt, перейти к числу 2.

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

Доказательство: Допустим, что на некотором этапе постоянные пометки дают длины кратчайших путей. Пусть S₁ – множество вершин с этими пометками, а S₂ – множество вершин с временными пометками. В конце шага 2 каждой итерации временная пометка l(x_i) дает кратчайший путь от S к x_i, проходящий полностью по вершинам S₁. Так как при каждой итерации в множестве S₁ включается только для вершин, то обновление пометки требует только одного сравнения на шаге 2. Пусть кратчайший путь от S к x_i^* не проходит целиком по S₁ и содержит по крайней мере одну вершину из S_2. Так как С_{i j} 0, то часть пути от x_j к x_i^* должна иметь неотрицательный вес. Δ и l (x_j) < l (x_j^*) - Δ < Δ (x_i^*). Это однако противоречит утверждению, что l (x_i^* j) – наименьшая временная пометка и, следовательно, кратчайший путь проходит полностью по вершинам множества S₁ и поэтому l (x_i^*) является его длиной. Так, множество S₁ равно {S} и при каждой итерации добавляется x_i^*, то предложение, что l(x₁) равно длине кратчайшего пути x_i S₁, выполняется при каждой итерации. Отсюда по индукции следует, что алгоритм дает оптимальный ответ.

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

Как только длины кратчайших путей от S будут найдены (они будут значениями пометок вершин), сами пути можно получить при помощи рекурсивной процедуры:

l (x_i^’) + l (x_i^’, x_i) = l (x_i)α.