Глава 21. Кратчайшие пути. определяемой всеми вершинами и ребрами, достижимыми из данного источника

⇐ ПредыдущаяСтр 155 из 230Следующая ⇒

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

Топологическая сортировка предоставляет непосредственное решение задачи кратчайших путей с несколькими источниками и множества других задач. Мы поддерживаем индексированный номерами вершин вектор wt, который содержит веса известных кратчайших путей из любого источника в каждую вершину. Чтобы решить задачу поиска кратчайших путей с несколькими источниками, мы инициализируем вектор wt значениями 0 для источников и большим сигнальным значением для всех остальных вершин. Затем мы обрабатываем эти вершины в топологическом порядке. Для обработки вершины v, для каждого отходящего ребра v-w мы выполняем операцию ослабления, которая обновляет кратчайший путь в w, если v-w лежит на более коротком пути из источника в w (проходящем через v). В процессе выполнения этих операций проверяются все пути из любой исходной вершины в каждую вершину в графе; операция ослабления отслеживает минимальную длину таких путей, и топологическая сортировка гарантирует, что мы обрабатываем вершины в подходящем направлении.

Мы можем реализовать этот метод непосредственно одним из двух способов. Первый заключается в добавлении нескольких строк кода к коду топологической сортировки в программе 19.8: просто после удаления вершины v из исходной очереди мы выполняем указанную операцию ослабления для каждого из ребер (см. упражнение 21.56). Второй способ предполагает топологическое упорядочение вершин и последующий проход по ним с выполнением операций ослабления так, как описано в предыдущем абзаце.

Программа 21.6. Наиболее длинные пути в ациклической сети________________________

Для нахождения наиболее длинных путей в ациклической сети мы рассматриваем вершины в топологическом порядке, и за счет выполнения для каждого ребра шага ослабления сохраняем в индексированном номером вершины векторе wt веса наиболее длинного известного пути в каждую вершину. Вектор Ipt определяет остовный лес наиболее длинных путей (с корнями в источниках) так, что path(v) возвращает последнее ребро в наиболее длинном пути, ведущем в v.

#include " dagTS.cc"

template < class Graph, class Edge> class LPTdag { const Graph & G; vector< double> wt; vector< Edge *> Ipt; public:

LPTdag(const Graph & G): G(G),

lpt(G.V()), wt(G.V<), 0) { int j, w; dagTS< Graph> ts(G);

for (int v = ts[j = 0]; j < G.V(); v = ts[++j]) { typename Graph:: adjIterator A(G, v);

for (Edge* e = A.beg();! A.end(); e = A.nxt()) if (wt[w = e-> w()] < wt[v] + e-> wt())

{ wt[w] = wt[v] + e-> wt(); lpt[w] = e; } } }

Edge *pathR(int v) const { return lpt[v]; } double dist(int v) const { return wt[v]; } };

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

Подобным же образом (с другими операциями ослабления) можно решить многие задачи обработки графов. Например, программа 21.6 демонстрирует реализацию второго подхода (сортировать, а затем сканировать) для решения задачи поиска наиболее длинных путей с несколькими источниками: для каждой вершины в сети определяется, какой путь является наиболее длинным из некоторого источника в эту вершину. Мы интерпретируем элемент wt, связываемый с каждой вершиной, как длину наиболее длинного известного пути из любого источника в эту вершину, инициализируем все веса значениями 0 и изменяем смысл сравнения в операции ослабления. На рис. 21.15 показана трассировка выполнения программы 21.6 на типовой ациклической сети.

Свойство 21, 9 Мы можем решить задачу поиска кратчайших путей с несколькими источниками и задачу поиска наиболее длинных путей с несколькими источниками в ациклических сетях за линейное время.

Доказательство: Одно и то же доказательство сохраняется для наиболее длинного пути, кратчайшего пути и многих других свойств пути. Ориентируясь на программу 21.6, мы проведем доказательство для случая наиболее длинных путей. Мы покажем методом индукции для параметра цикла i, что для всех вершин v = ts [j] для j < i, которые уже были обработаны, wt[v] есть длина наиболее длинного пути из источника в v. При v = ts[i] пусть t будет вершиной, предшествующей v на некотором пути из источника в v. Поскольку вершины в векторе ts расположены в топологически отсортированном порядке, то t наверняка была уже обработана. По предположению индукции, wt[t] представляет собой длину наиболее длинного пути, ведущего в t, и шаг ослабления в программе проверяет, будет ли путь в v через t более длинным. Из предположения индукции также следует, что все пути, ведущие в v, будут проверены, как только v будет обработана. ■

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

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

Как мы знаем из главы 19, абстракция DAG является общим понятием, используемым во многих приложениях. Например, в разделе 21.6 мы увидим приложение, которое кажется не связанным с сетями, но которое может непосредственно задействовать программу 21.6.

Далее мы снова возвращаемся к задаче о кратчайших путях для всех пар в ациклических сетях. Как и в разделе 19.3, один из методов, которые можно было бы использовать для решения этой задачи, предполагает выполнение в отношении каждой вершины алгоритма для единственного источника (см. упражнение 11.65). Столь же эффективный подход, который мы рассматриваем здесь, заключается в применении единственного DFS с

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

РИСУНОК 21.15. ВЫЧИСЛЕНИЕ НАИБОЛЕЕ ДЛИННЫХ ПУТЕЙ В АЦИКЛИЧЕСКОЙ СЕТИ

В этой сети каждое ребро имеет вес (показанный вверху слева), связываемый с вершиной, из которой оно исходит. Стоки имеют ребра к фиктивной вершине 10, которая на рисунках не показана. Массив wt содержит длину наиболее длинного известного пути в каждую вершину из некоторого источника, а массив st хранит предыдущую вершину на наиболее длинном пути. Этот рисунок иллюстрирует действие программы 21.6, которое производит выбор из источников (затененные узлы на каждой диаграмме) по дисциплине FIFO, хотя на каждом шаге могли бы выбираться любые источники. Мы начинаем с удаления 0 и проверки каждого из ее смежных ребер, обнаруживая однореберные пути длины 0.41, ведущие в 1, 7 и 9. Затем мы удаляем 5 и записываем однореберный путь из 5 в 10 (слева, второй сверху). Далее, мы удаляем 9 и записываем пути 0-9-4 и 0-9-6 длины 0.70 (слева, третий

сверху). Мы продолжаем эти действия, изменяя массивы каждый раз, когда находим более длинные пути. Например, когда мы удаляем 7 (слева, второй снизу), мы записываем пути длины 0.73, ведущие в 8 и 3; затем, позже, когда мы удаляем 6, мы записываем более длинные пути (длины 0.91,) в 8 и 3 (справа, вверху). Цель вычислений заключается в нахождении наиболее длинного пути к фиктивному узлу 10. В данном случае результатом будет путь 0-9-6-8-2 длины 1, 73.

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

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

Программа 21.7. Все кратчайшие пути в ациклической сети__________________________

Эта реализация интерфейса из программы 21.2 для взвешенного DAG получена путем добавления соответствующих операций ослабления к основанной на динамическом программировании функции транзитивного замыкания из программы 19.9.

template < class Graph, class Edge> class allSPdag { const Graph & G;

vector < vector < Edge *> > p; vector < vector < double> > d; void dfsR(int s)

{ typename Graph:: adjIterator A(G, s); for (Edge* e = A.beg();! A.end(); e = A.nxt()) { int t = e-> w(); double w = e-> wt(); if (d[s][t] > w)

{ d[s][t] = w; p[s][t] = e; > if < p[t][t] ==0) dfsR(t); for (int i = 0; i < G.V(); i++) if (p[t][i]) if (d[s][i] > w + d[t][i])

{ d[s][i] = w + d[t][il; p[s][i] = e; } } }

public:

allSPdag(const Graph & G): G(G),

p(G.V()), d(G.V()) { int V = G.V(); for (int i = 0; i < V; i++)

{ p[i].assign(V, 0); d[i].assign(V, V); } for (int s = 0; s < V; s++) if (p[s][s] == 0) dfsR(s); } Edge *path(int s, int t) const

{ return p[s][t]; } double dist(int s, int t) const { return d[s][t]; }

Программа 21.7 является реализацией сказанного. Применение этой программы к типовому взвешенному DAG иллюстрируется на рис. 21.16. Если не касаться вопроса ослабления, то можно сказать, что есть одно важное различие между этим вычислением и вычислением транзитивного замыкания для DAG: в программе 19.9 у нас была возможность игнорировать ребра в дереве DFS, поскольку они не предоставляют новой информации о достижимости, однако в программе 21.7, тем не менее, мы должны рассмотреть все ребра, поскольку любое ребро могло бы привести к более короткому пути.

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

РИСУНОК 21.16. КРАТЧАЙШИЕ ПУТИ В АЦИКЛИЧЕСКОЙ СЕТИ

Эта схема показывает вычисление матрицы (справа внизу) всех кратчайших расстояний для типового взвешенного DAG (вверху слева); каждая строка вычисляется в результате последнего действия в рекурсивной функции DFS. Каждая строка вычисляется из строк для смежных вершин, которые появляются раньше в списке, поскольку строки вычисляются в топологически обратном порядке (обратный порядок обхода дерева DFS, которое изображено слева внизу). Массив сверху справа показывает строки матрицы в порядке их вычисления. Например, чтобы вычислить каждый элемент в строке для 0, мы добавляем 0.41 к соответствующему элементу в строке для 1 (чтобы получить расстояние к этой вершине из 0 после получения 0-1,), затем добавляем 0.45 к соответствующему элементу в строке для 3 (чтобы получить расстояние к этой вершине из 0 после получения 0-3) и, наконец, выбираем меньшее из этих двух значений. Вычисления, по существу, оказываются теми же, что и в случае транзитивного замыкания DAG (см., например, рис. 19.23). Наиболее значительное различие между ними состоит в том, что алгоритм транзитивного замыкания мог бы игнорировать ребра (как например, 1-2 в этом примере), поскольку они ведут к вершинам, относительно которых известно, что они достижимые, в то время как алгоритм кратчайших путей должен проверить, являются ли пути, связываемые с нижними ребрами, более короткими, чем уже известные пути. Если бы мы должны были игнорировать 1-2 в этом примере, то должны были бы пропустить кратчайшие пути 0-1-2 и 1-2.

Свойство 21.10. Мы можем решить задачу поиска кратчайших путей для всех пар на ациклических сетях с единственным DFS за время, пропорциональное VE.

Доказательство: Справедливость этого утверждения вытекает непосредственно из стратегии решения задачи с единственным источником для каждой вершины (см. упражнение 21.65). Мы можем также установить его методом индукции, из программы 21.7. После рекурсивных вызовов для вершины v мы знаем, что вычислены все кратчайшие пути для каждой вершины в списке смежных с v, так что мы можем найти кратчайшие пути из v в каждую вершину за счет проверки каждого ребра, инцидентного v. Мы выполняем E шагов ослабления для каждого ребра, а в общей сложности VE шагов ослабления. ■

Таким образом, топологическая сортировка для ациклических сетей позволяет избежать затрат на очередь с приоритетами в алгоритме Дейкстры. Подобно алгоритму Флойда, программа 21.7 также решает задачи, более общие, чем те, которые решаются алго-

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

РИСУНОК 21.17. ВСЕ НАИБОЛЕЕ ДЛИННЫЕ ПУТИ В АЦИКЛИЧЕСКОЙ СЕТИ

Наш метод для вычисления всех кратчайших путей в ациклических сетях работает даже при наличии отрицательных весов. Следовательно, его можно использовать для вычисления наиболее длинных путей прежде всего за счет инвертирования всех весов, как показано здесь для сети из рис. 21.16. Наиболее длинным простым путем веса 1.73 в этой сети является 0-1-5-4-2-3.

ритмом Дейкстры, поскольку, в отличие от алгоритма Дейкстры (см. раздел 21.7), этот алгоритм работает правильно даже при наличии отрицательных весов ребер. Если мы выполняем этот алгоритм после инвертирования всех весов в ациклической сети, он находит все наиболее длинные пути, как показано на рис. 21.17. Или же можно найти наиболее длинные пути с помощью обращения проверки неравенства в алгоритме ослабления, как в программе 21.6.

Остальные алгоритмы для нахождения кратчайших путей в ациклических сетях, которые упоминаются в начале этого раздела, некоторым образом обобщают методы из главы 19 подобно другим алгоритмам, которые рассматривались в этой главе. Их реализация является путем, приводящим в результате к укреплению вашего понимания как DAG, так и кратчайших путей (см. упражнения 21.62-21.65). Все эти методы выполняются за время, пропорциональное VE в худшем случае, с фактическими затратами, зависящими от структуры DAG. В принципе, мы могли бы дать даже лучшую оценку для некоторых разреженных взвешенных DAG (см. упражнение 19.117).

⇐ Предыдущая 150 151 152 153 154155156 157 158 159 Следующая ⇒

Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2025 год. (0.011 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал