Сетевое математическое моделирование потоков. Графовые модели. Задачи о кратчайшем пути

Глава 5. Сетевое математическое моделирование потоков

Графовые модели

Задачи о кратчайшем пути

Алгоритм кратчайшего пути с неотрицательной матрицей весов

Пусть задан ориентированный граф G = (X,U), где X = {x₁, x₂, … , x_n} – множество вершин графа, U = {u₁, u₂, … , u_m} – множество дуг u_ij=(x_i, x_j), x_i, x_j Є X, причем каждой дуге приписан неотрицательный вес (число, большее или равное нулю) С = {c₁, c₂, … ,c_m}, c_i >= 0. Необходимо найти кратчайший путь (длина пути определяется как сумма весов дуг, входящих путь) от x_s (начальная вершина) к x_t (конечная вершина).

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

Совершенно очевидно, что данная задача имеет решение, если существует путь от вершины x_s к вершине x_t,

Граф задается матрицей весов С = ║с_ij║ (i,j = 1, 2, … , n), с_ij >= 0, причем если с_ij > 0, то существует дуга от вершины x_s к вершине x_t.

1.  Приписываем вершине x_s (начальная вершина) постоянную метку l(x_s)* = 0. Всем остальным меткам приписываем временные метки, равные бесконечности  l(x_i) = ∞  (i = 1, 2, … , n; i ≠ s). Вектор меток будет равен L = (0*, ∞, … , ∞) (звездочкой отмечена постоянная метка). Вектор пути D = (x_s). Пусть x_k = x_s.

2.  Для всех вершин x_i, для которых c_ki > 0 и имеющих временные метки, изменить метки в соответствии со следующим  выражением: l(x_i) = min [l(x_i), l(x_k) + c(x_k, x_i)]. Если таких вершин x_i нет, то задача не имеет решения, т.е. пути от вершины x_s к вершине x_t в заданном графе не существует (конец алгоритма).

3.  В векторе пометок L найти временную метку с минимальным значением l(x_j) =  min [l (x_i)] (это значение не должно быть равным бесконечности). Данную метку сделать постоянной l*(x_j). Вершину x_j заносим в вектор пути D = (x_s, … , x_j). Положить x_k = x_j.

4.  Если x_k = x_t, то конец алгоритма, иначе перейти к пункту 2.

Значение метки l*(x_t) будет равно значению кратчайшего пути от вершины x_s к вершине x_t в заданном графе.

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

Пример

Рассмотрим граф, изображенный на рис. 5.1, где каждое неориентированное ребро рассматривается как пара противоположно ориентированных   дуг   равного   веса

Рис.5.1

Матрица весов С приведена ниже:

Алгоритм кратчайшего пути с произвольной матрицей весов

Только что описанный алгоритм Дейкстры применим лишь в том случае, когда c_ij ≥ 0 для всех i и j. Однако если матрица C является матрицей стоимостей, то дуги, приносящие доход, должны иметь отрицательные «стоимости». В этом случае для нахождения кратчайших путей между вершиной s и всеми другими вершинами можно воспользоваться описанной ниже процедурой. Этот метод также является итерационным и основан на пометках вершин, причем в конце k-й итерации пометки равны длинам тех кратчайших путей (от s ко всем остальным вершинам), которые содержат не более k +1 дуг. В отличие от алгоритма Дейкстры никакая из пометок во время этого процесса не рассматривается как окончательная