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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Доказательство: Допустим, что на некотором этапе постоянные пометки дают длины кратчайших путей. Пусть S1 – множество вершин с этими пометками, а S2 – множество вершин с временными пометками. В конце шага 2 каждой итерации временная пометка l(xi) дает кратчайший путь от S к xi, проходящий полностью по вершинам S1. Так как при каждой итерации в множестве S1 включается только для вершин, то обновление пометки требует только одного сравнения на шаге 2. Пусть кратчайший путь от S к xi * не проходит целиком по S1 и содержит по крайней мере одну вершину из S2. Так как Сi j 0, то часть пути от xj к xi * должна иметь неотрицательный вес. Δ и l (xj) < l (xj * ) - Δ < Δ (xi * ). Это однако противоречит утверждению, что l (xi * j) – наименьшая временная пометка и, следовательно, кратчайший путь проходит полностью по вершинам множества S1 и поэтому l (xi * ) является его длиной. Так, множество S1 равно и при каждой итерации добавляется xi * , то предложение, что l(x1) равно длине кратчайшего пути xi S1, выполняется при каждой итерации. Отсюда по индукции следует, что алгоритм дает оптимальный ответ.

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

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