Глава 21. Кратчайшие пути. Определение 21.2.Пусть задана сеть и некоторая вершина s, деревом кратчайших пу­тей(SPT, Shortest-Paths Tree) для s будет подсеть

Определение 21.2. Пусть задана сеть и некоторая вершина s, деревом кратчайших пу­тей (SPT, Shortest-Paths Tree) для s будет подсеть, содержащая s и все вершины, дости­жимые из 5, образующая направленное дерево с корнем в s такое, что каждый путь в де­реве является кратчайшим путем в сети.

Возможно существование нескольких путей одной и той же длины, соединяющих за­данную пару узлов, так что SPT не обязательно уникальны. Вообще, как видно из рис. 21.2, если мы выбираем кратчайшие пути из вершины s в каждую вершину, достижимую из s в сети, и из подсети, порожденной ребрами этих путей, мы можем получить DAG. Различные кратчайшие пути, соединяющие пары узлов, могут рассматриваться как под-пути некоторого более длинного пути, содержащего оба узла. Благодаря такой особенно­сти, мы обычно ограничиваемся вычислением любого SPT для данного орграфа и началь­ной вершины.

Наши алгоритмы в общем случае инициализируют элементы вектора wt некоторым сигнальным значением. Упомянутая величина должна быть достаточно малой, чтобы ее добавление при проверке ослабления не вызывало переполнения, и достаточно большой, чтобы никакой простой путь не имел большего веса. Например, если веса ребер находят­ся между 0 и 1, в качестве сигнального значения можно выбрать V. Имейте в виду, что следует соблюдать особую осторожность при проверке наших допущений, когда сигналь­ные значения используются в сетях, которые в принципе могут иметь отрицательные веса. Например, если обе вершины имеют сигнальные значения, то код ослабления не выпол­нит никаких действий, если e.wt не отрицательно (что, вероятно, будет иметь место в боль­шинстве реализаций), однако изменит wt[w] и spt[w], если этот вес отрицателен.

Наш код всегда использует вершину назначения (адресат) в качестве индекса для со­хранения ребер SPT (spt[w]-> w() == w). Для краткости и согласованности с главами 17-19 мы применяем обозначение st[w] для ссылки на вершину spt[w]-> v() (в тексте и особенно на рисунках), дабы подчеркнуть, что вектор spt является действительно пред­ставлением родительской связи в дереве кратчайших путей (см. рис. 21.6). Вычислить кратчайший путь из s в / можно, продвигаясь по дереву от t к s; когда мы делаем это, то проходим по ребрам в направлении, противоположном их направлению в сети, и захо­дим в вершины пути в обратном порядке (t, st[t], st[st[t]] и т.д.).

Один из способов получения ребер из SPT на пути в порядке следования от источни­ка к стоку предполагает использование стека. Например, следующий код выводит путь из источника в заданную вершину w:

stack < ED6E *> Р; EDGE *e = spt[w]; while (e) { P.push (e); e = spt [e-> v() ]); } if (P.empty()) cout «P. top () -> v(); while (! P.empty())

{ cout «" -" «P.top()-> w(); P.pop(); }

В реализации класса мы могли бы использовать аналогичный код для того, чтобы кли­ент смог получить вектор, содержащий ребра пути.

Если необходимо просто распечатать или иным способом обработать ребра пути, про­хождение всего пути в обратном порядке для достижения первого ребра может оказать­ся нежелательным. Один из подходов, позволяющих обойти упомянутое затруднение, зак­лючается в том, чтобы работать с обратной сетью, как показано на рис. 21.6.

Часть 5. Алгоритмы на графах

РИСУНОК 21.6. ДЕРЕВЬЯ КРАТЧАЙШИХ ПУТЕЙ

Кратчайшие пути из 0 к другим узлам в этой сети — это 0-1, 0-5-4-2, 0-5-4-3, 0-5-4 и 0-5, соответственно. Эти пути определяют остовное дерево, которое дано в трех представлениях (серые ребра в изображении сети, ориентированное дерево и родительские связи с весами) в центре. Связи в представлении родительских связей (то, что обычно вычисляется), ориентированы в противополож­ном направлении по сравнению со связями в орграфе, так что мы иногда работаем с обратным орграфом. Остовное дерево, определяемое кратчайшими путями из 3 в каждый из других узлов в обратном представлении, показано справа. Представление этого дерева в виде родительских связей дает кратчайшие пути из каждого из других узлов в 2 в исходном графе. Например, мы можем найти кратчайший путь 0-5-4-3 из 0 в 3, следуя по связям st[0] = 5, st[5] = 4 и st[4] = 3.

Мы используем обратный порядок и ослабление ребра дkя задач определения кратчай­ших путей из единственного источника, поскольку SPT дает компактное представление кратчайших путей из источника во все другие вершины в векторе с точно V входами.

Теперь мы рассмотрим ослабление пути, которое является основой некоторых наших алгоритмов для поиска всех пар: дает ли прохождение через данную вершину более ко­роткий путь, соединяющий две других заданных вершины? Например, предположим, что имеются три вершины s, х и t, и мы хотим знать, что лучше, пройти из s в х, а затем из х в t, или сразу пройти из s в t, не заходя в х. Для прямолинейных соединений на эвклидо­вом пространстве неравенство треугольника говорит нам, что маршрут через х не может быть более коротким, чем прямой маршрут из s в t, но для путей на сети это вполне воз­можно (см. рис. 21.7). Чтобы определить, как именно обстоят дела, нам нужно знать дли­ны путей из s в х, из х в t и остальных, ведущих из s в t (но не включающих х). Затем мы просто проверяем, меньше ли сумма первых двух, чем третий; если это так, то мы дол­жны соответствующим образом обновить наши данные.

Ослабление пути подходит для решения задачи всех пар, где мы сохраняем длины крат­чайших путей между всеми парами тех вершин, которые встречались до сих пор. В част­ности, в коде вычисления кратчайших путей для всех пар этого вида мы поддерживаем вектор векторов d такой, что d[s][t] есть длина кратчайшего пути из s в t. Кроме того, мы также поддерживаем вектор векторов р такой, что p[s][t] есть следующая вершина на кратчайшем пути из s в t. Первый из них носит название матрицы расстояний, а второй — матрицы путей. На рис. 21.8 показаны две упомянутых матрицы для сети нашего приме­ра. Матрица расстояний является главной целью вычислений, а матрица путей использу­ется из-за того, что она явно более компактна, хотя и несет ту же информацию, что и полный список путей, который показан на рис. 21.3.