![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Кратчайшиепути
аждый путь во взвешенном орграфе ассоциируется с весом пути (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. Кратчайшие пути
Все свойства связности ориентированного графа, которые мы рассматривали в главе 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. Алгоритмы на графах
Предположим, что в вышеприведенном определении некоторая вершина на пути из s в t принадлежит также некоторому отрицательному циклу. В этом случае существование (непростого) кратчайшего пути из s в t должно вызвать противоречие, поскольку мы могли бы использовать цикл для создания пути, который имел бы вес ниже, чем любое заданное значение. Чтобы устранить такое противоречие, в данном определении мы ограничиваемся простыми путями так, чтобы понятие кратчайшего пути можно было строго определить для любой сети. Тем не менее, до раздела 21.7 мы не рассматриваем отрицательных циклов в сетях, поскольку, как там будет показано, они представляют собой поистине принципиальное препятствие при решении проблем кратчайших путей. Чтобы найти кратчайшие пути во взвешенном неориентированном графе, мы строим сеть с теми же вершинами и с двумя ребрами (по одному в каждом направлении), которые соответствуют каждому ребру в исходном графе. Существует взаимно однозначное соответствие между простыми путями в сети и простыми путями в графе, а стоимости путей одни и те же; таким образом, проблемы кратчайших путей для них эквивалентны. В самом деле, когда мы строим стандартные списки смежности или представление взвешенного неориентированного графа в виде матрицы смежности, мы строим точно такую же сеть (см., например, рис. 20.3). Такая конструкция не будет продуктивной, если веса могут быть отрицательными, поскольку при этом получаются отрицательные циклы в сети, а мы не знаем, как решать проблемы кратчайших путей в сетях с отрицательными циклами (см. раздел 21.7). Другими словами, алгоритмы для сетей, которые мы излагаем в этой главе, работают также и для взвешенных неориентированных графов. В определенных приложениях удобно вместо ребер присваивать веса вершинам, либо дополнительно рассматривать веса на ребрах; мы также могли бы рассмотреть более сложные задачи, где имеют значение как количество ребер в пути, так и общий вес пути. Мы можем ставить подобные задачи, формулируя их в терминах сетей со взвешенными ребрами (см., например, упражнение 21.4) или несколько расширив базовые алгоритмы (см., например, упражнение 21.52). Поскольку различия ясны из контекста, мы не вводим специальную терминологию, позволяющую отличать кратчайшие пути во взвешенных графах от кратчайших путей в графах, которые не имеют весов (где вес пути есть просто число составляющих его ребер — см. раздел 17.7). Поскольку частные задачи, которые могут быть поставлены на
|