Кратчайшиепути

аждый путь во взвешенном орграфе ассоциируется с весом пути (path weight), величиной, представляющей со­бой сумму весов ребер, составляющих этот путь. Это обсто­ятельство позволяет нам сформулировать такую задачу как " найти путь между двумя заданными вершинами, имеющий минимальный вес". Задачи о кратчайших путях и являются темой данной главы. Постановки такого рода не только ин­туитивно подходят для описания многих проблемно-ориенти­рованных приложений, они также вводят нас в тот могучий мир, где мы будем искать эффективные алгоритмы решения задач в общем виде, которые применимы к широкому кру­гу реальных приложений.

Некоторые из рассматриваемых в данной главе алгорит­мов непосредственно связаны с алгоритмами, изучавшими­ся в главах 17-20. Введенная нами система понятий поиска на графе здесь применима непосредственно, и некоторые из специфических механизмов, использованных в главах 17 и 19 для выражения отношения связности в графах и орграфах, создают основу для решения задач о кратчайших путях.

Для краткости взвешенные орграфы мы будем называть сетями (networks). На рис. 21.1 показан пример сети и ее стандартные представления. Ранее в разделе 20.1 мы уже раз­работали интерфейс АТД с матрицей смежности и реализа­цией класса списков смежности — в вызове конструктора следует только передать true в качестве второго аргумента так, чтобы класс содержал одно представление каждого реб­ра, так же как это делалось в главе 19 при получении пред­ставлений орграфов из представлений неориентированных графов из главы 17 (см. программы 20.1-20.4).

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

РИСУНОК 21.1. ПРИМЕР СЕТИ И ЕЕ ПРЕДСТАВЛЕНИЯ

Эта сеть (взвешенный орграф) представлена четырьмя различными способами: в виде списка ребер, в графическом виде, с помощью матрицы смежности и в виде списка смежных вершин. Как и для алгоритмов MST, в клетках матрицы и в узлах списка мы показываем весь., но в программах использу­ем указатели на ребра. Хотя на рисунке мы часто изображаем длины ребер пропорциональными их весам (как это делалось для алгоритмов MST), мы не настаиваем на этом правиле, поскольку большинство алгоритмов поиска кратчайших путей могут иметь произвольные неотрицательные веса (отрицательные веса приводят к дополнительным сложностям). Матрица смежности не является симметричной, а списки смежности содержат один узел для каждого ребра (как в невзве­шенном орграфе). Несуществующие ребра представляются пустыми клетками в матрице (незапол­ненные места на рисунке) и вообще отсутствуют в списках (ребер). Петли длины 0 введены потому, что при этом упрощается реализация алгоритмов кратчайших путей. Для экономии места они не представлены в списке ребер слева и нужны для того, чтобы показать типичную последовательность действий, когда мы добавляем их по соглашению, при создании матрицы смежности или представле­ния в виде списков смежности.

Как подробно пояснялось в главе 20, мы используем указатели на абстрактные ребра взвешенного орграфа, чтобы расширить применимость полученных реализаций. При та­ком подходе для орграфов проявляются некоторые заслуживающие внимания отличия по сравнению с тем, что мы имели для неориентированных графов в разделе 20.1. Во-пер­вых, поскольку имеется только одно представление каждого ребра, нам не нужно вызы­вать функцию from() в классе ребра (см. программу 20.1) при использовании итератора: в орграфе значение e-> from(v) истинно для каждого указателя ребра е, возвращаемого итератором для v. Во-вторых, как было показано в главе 19, часто при обработке оргра­фа полезно иметь возможность работать с его обратным графом, но нам потребуется под­ход, отличный от того, который был принят в программе 19.1, поскольку та реализация создает ребра, образующие обратный граф, тогда как мы предполагаем, что клиенты АТД графа, предоставляющие указатели на ребра, не должны создавать петель (см. упражне­ние 21.3).

В приложениях или системах могут потребоваться любые типы графов; на этот случай имеется упражнение, суть которого заключается в разработке такого АТД сети, из кото­рого можно создать производные АТД для невзвешенных неориентированных графов из глав 17 и 18, невзвешенных орграфов из главы 19 или взвешенных неориентированных графов из главы 20 (см. упражнение 21.10).

Когда мы имеем дело с сетями, в общем случае удобно оставлять петли во всех пред­ставлениях. Такое соглашение придает алгоритмам гибкость, позволяя использовать по­рог максимального значения веса, чтобы указать, что из вершины не может исходить реб­ро, направленное в нее же. В наших примерах мы используем петли веса 0, хотя петли с положительным весом, конечно, имеют смысл во многих приложениях. Многие прило­жения также требуют наличия параллельных ребер, возможно, с отличающимися весами.

Глава 21. Кратчайшие пути

Как упоминалось в разделе 20.1, различные варианты для игнорирования или создания комбинации подобных ребер присущи и ряду других приложений. Для упрощения в этой главе ни один из наших примеров не использует параллельных ребер, и мы не допуска­ем параллельных ребер в представлении с помощью матрицы смежности; мы также не проверяем наличия параллельных ребер, и не удаляем их из списков смежности.

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

Определение 21.1. Кратчайшим путем между двумя вершинами s и t в сети называется такой направленный простой путь из s в t, что никакой другой путь не имеет более низ­кого веса.

Это определение лаконично, однако за его краткостью скрываются все достоинства. Во-первых, если t не достижима из s, то никакого пути не существует вообще, а, следо­вательно, нет и кратчайшего пути. Для удобства рассматриваемые алгоритмы часто трак­туют этот случай как эквивалент ситуации, в которой между s и t существует путь с бес­конечным весом. Во-вторых, как и в случае алгоритмов MST (Minimal Spanning Tree, минимальное остовное дерево; в литературе также встречается эквивалентное сокраще­ние — SST, Shortest Spanning Tree - прим. перев.), мы используем сети, где в примерах веса ребер пропорциональны длинам ребер, однако наше определение не содержит это­го требования, поэтому в алгоритмах (кроме одного в разделе 21.5) подобное допущение не делается. Действительно, алгоритмы для наиболее коротких путей предстают в своем лучшем виде, когда они находят алогичные кратчайшие пути, как, например, путь меж­ду двумя вершинами, который проходит через несколько других вершин, но имеет общий вес меньше веса ребра, непосредственно соединяющего эти вершины. В-третьих, может существовать несколько путей с одним и тем же весом из одной вершины в другую, и мы обычно удовлетворяемся тем, что выделяем один из них. На рис. 21.2 показан пример с проставленными весами, который иллюстрирует эти замечания.

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

Дерево кратчайших путей (SPT, Shortest-Path Tree) определяет наиболее короткие пути из корня в другие вершины (см. определение 21.2). В общем случае, различные пути могут иметь одну и ту же длину, так что может существовать несколько SPT, определяющих кратчайшие пути из данной вершины. В сети данного примера, показанной слева, все кратчайшие пути из 0 есть подграфы графа DAG, показанного справа от сети. Дерево с корнем в 0является подграфом этого DAG тогда и только тогда, когда оно является SPT для 0. Два дерева справа представляют собой подобные деревья.

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