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

Основные принципы

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

Наши алгоритмы основываются на многократном применении одной из двух операций релаксации:

Релаксация ребра. Проверка, дает ли продвижение по данному ребру новый кратчайший путь к конечной вершине.

Релаксация пути. Проверка, дает ли прохождение через данную вершину новый кратчайший путь, соединяющий две другие заданных вершины.

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

(рис 21.5) Релаксация ребра

Здесь показана операция релаксации, лежащая в основе наших алгоритмов поиска кратчайших путей из одного истока. Мы прослеживаем известные кратчайшие пути из истока s в каждую вершину и проверяем, образует ли ребро v-w более короткий путь в w. В верхнем примере это не так, поэтому ребро игнорируется. В нижнем примере получается более короткий путь - значит, нужно обновить структуры данных, чтобы указать, что лучший известный путь из s в w проходит через v, завершаясь ребром v-w.

Сначала рассмотрим релаксацию ребра (см. рис 21.5). Все рассматриваемые нами алгоритмы поиска кратчайших путей из одного истока основаны на следующем шаге: приводит ли данное ребро к рассмотрению более короткого пути из истока к конечной вершине этого ребра?

Структуры данных, необходимые для выполнения этих действий, просты. Во-первых, наша основная задача состоит в вычислении длины кратчайших путей из истока в каждую из прочих вершин. Условимся сохранять длины известных кратчайших путей из истока в каждую из вершин в векторе wt, индексированном именами вершин. Во-вторых, для записи самих путей продвижения от вершины к вершине мы будем придерживаться того же соглашения, что и в других алгоритмах поиска на графах в лекциях 18-20: мы используем индексированный именами вершин вектор spt для записи последнего ребра на кратчайшем пути из истока в данную индексированную вершину. Эти ребра составляют дерево.

Теперь реализация релаксации ребра выполняется просто.

При поиске кратчайших путей из одного истока следующий код выполняет релаксацию вдоль ребра e, направленного от v к w:

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

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

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

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

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

В качестве индекса для сохранения ребер SPT (). Для вычисления кратчайшего пути из s в t нужно подняться по дереву от t к s; при этом мы проходим по ребрам в направлении, противоположном их ориентации в сети, и посещаем вершины пути в обратном порядке (t, st[t], st[st[t]] и т.д.).

(рис 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.

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

  stack <EDGE *> P; 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. В задачах с одним истоком мы используем обратный порядок и релаксацию ребер, поскольку SPT дает компактное представление кратчайших путей из истока во все другие вершины в векторе, который содержит лишь V элементов.

(рис 21.7) Релаксация пути

Здесь продемонстрирована операция релаксации, на которой основаны наши алгоритмы поиска кратчайших путей для всех пар вершин. Мы отслеживаем лучший известный путь между всеми парами вершин и проверяем, может ли вершина i улучшить путь из s в t. В верхнем примере это не так, а в нижнем путь можно улучшить. Когда встречается такая вершина i, что сумма длины известного кратчайшего пути из s в i и длины известного кратчайшего пути из i в t меньше длины известного кратчайшего пути из s в t, мы обновляем наши структуры данных, чтобы указать, что теперь известен более короткий путь из s в t (в направлении к i).

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

Релаксация пути входит в решение задачи для всех пар вершин, где мы храним длины найденных на данный момент кратчайших путей между всеми парами вершин. А именно, в коде вычисления кратчайших путей для всех пар вершин мы используем вектор векторов d - такой, что значение d[s][t] содержит длину кратчайшего пути из s в t, и вектор векторов p - такой, что p[s][t] содержит следующую вершину на кратчайшем пути из s в t. Первый вектор называется матрицей расстояний, а второй - матрицей путей.

На рис 21.8 показаны эти матрицы для нашей демонстрационной сети. Главной целью вычислений является матрица расстояний, а матрица путей используется потому, что она явно более компактна, хотя и содержит ту же информацию, что и полный список путей, приведенный на рис 21.3.

(рис 21.8) Все кратчайшие пути

Две матрицы справа - компактные представления всех кратчайших путей для демонстрационной сети, приведенной слева. Они содержат ту же информацию, что и список на рис 21.3. Матрица расстояний слева содержит длины кратчайших путей: значение элемента на пересечении строки s и столбца t равно длине кратчайшего пути из s в t. Матрица путей справа содержит информацию, необходимую для обхода пути: элемент на пересечении строки s и столбца t содержит следующую вершину на пути из s в t.

При наличии этих структур данных релаксация пути выражается следующим кодом:

  if (d[s][t] > d[s][x] + d[x][t])
    { d[s][t] = d[s][x] + d[x][t]; p[s][t] = p[s][x]; }
      

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

Лемма 21.1. Если вершина x лежит на кратчайшем пути из s в t, то этот путь состоит из кратчайшего пути из s в x, за которым следует кратчайший путь из x в t.

Доказательство. Если бы это было не так, мы могли бы воспользоваться любым более коротким путем из s в x или из x в t для построения более короткого пути из s в t. $$$\blacksquare$$$

Мы сталкивались с операцией релаксации пути при рассмотрении алгоритмов транзитивного замыкания в . Если веса ребер и путей либо равны 1, либо бесконечны (т.е. вес пути равен 1 только если все его ребра имеют единичный вес), то релаксация пути - это операция, которая использовалась в алгоритме Уоршалла (если существуют пути из s в x и из x в t, то существует и путь из s в t). Если определить вес пути как количество ребер в этом пути, то алгоритм Уоршалла обобщает алгоритм Флойда для нахождения всех кратчайших путей в невзвешенном орграфе. Как будет показано в разделе 21.3, его можно обобщить еще дальше - применительно к сетям.

С математической точки зрения важно, что все эти алгоритмы можно привести к унифицированному алгебраическому виду, который помогает их пониманию. С точки зрения программиста важно, что каждый из этих алгоритмов можно реализовать, используя абстрактную операцию + (для вычисления веса пути из весов ребер) и абстрактную операцию < (для вычисления минимального значения из множества весов путей) - исключительно в контексте операции релаксации (см. упражнения 19.55 и 19.56).

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

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

Итак, релаксация предоставляет базовые абстрактные операции, необходимые для построения алгоритмов поиска кратчайших путей. Основная сложность здесь - выбор, указывать ли начальное или конечное ребро в кратчайшем пути. Например, алгоритмы для одного истока более естественно выражаются при задании пути конечным ребром: тогда для реконструкции пути потребуется только один индексированный именами вершин вектор, поскольку все пути ведут обратно к истоку. Этот выбор не представляет принципиальной трудности, поскольку можно либо использовать обратный граф, либо добавить функции-члены, которые скрывают разницу от клиентов. Например, в интерфейсе можно определить функцию-член, которая возвращает ребра кратчайшего пути в векторе (см. упражнения 21.15 и 21.16).

Поэтому для простоты все наши реализации в этой главе содержат функцию-член dist, которая возвращает длину кратчайшего пути и либо функцию-член path, возвращающую начальное ребро в кратчайшем пути, либо функцию-член pathR, которая возвращает конечное ребро в кратчайшем пути. К примеру, наши программы для одного истока, в которых применяется релаксация ребра, обычно реализуют эти функции так:

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

Аналогично, реализации поиска всех путей, которые используют релаксацию пути, обычно реализуют эти функции так:

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

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

(рис 21.9) Все кратчайшие пути в сети

Здесь показаны SPT-деревья для каждой вершины в обращении сети с рис 21.8 (от 0 до 5, сверху вниз): в виде поддеревьев сети (слева), ориентированных деревьев (в центре) и представления родительскими ссылками, вместе с индексированным именами вершин массивом длин путей (справа). Объединение этих массивов формирует матрицы путей и расстояний (где каждый массив становится столбцом) и дает решение задачи о кратчайших путях для всех пар вершин, которая показана на рис 21.8.

Упражнения

21.12. Нарисуйте SPT из вершины 0 для сети, определенной в упражнении 21.1, и для ее обращения. Приведите представление родительскими ссылками для обоих деревьев.

21.13. Считайте ребра в сети, определенной в упражнении 21.1, неориентированными ребрами - когда каждому ребру в сети соответствуют два разнонаправленных ребра равного веса. Выполните упражнение 21.12 для этой сети.

21.14. Измените на рис 21.2 направление ребра 0-3. Нарисуйте два различных SPT с корнем в вершине 2 для этой измененной сети.

21.15. Напишите функцию, которая использует функцию-член pathR из реализации задачи для одного истока и помещает в контейнер vector из библиотеки STL указатели на ребра пути из истока v в заданную вершину w.

21.16. Напишите функцию, которая использует функцию-член path из реализации задачи для всех путей и помещает в контейнер vector из библиотеки STL указатели на ребра пути из заданной вершины v в другую заданную вершину w.

21.17. Напишите программу, которая использует функцию из упражнения 21.16 для вывода всех путей в стиле рис 21.3.

21.18. Приведите пример, который показывает, как можно найти кратчайший путь из s в t, не зная длину более короткого пути из s в х для некоторого х.

Алгоритм Дейкстры

В был рассмотрен алгоритм Прима для нахождения минимального остовного дерева (MST) взвешенного неориентированного графа: мы строим его, добавляя на каждом шаге кратчайшее ребро, которое соединяет вершину из MST с вершиной, еще не входящей в MST. Для вычисления SPT можно воспользоваться почти такой же схемой. Вначале мы заносим в SPT исток, а затем строим SPT, добавляя на каждом шаге одно ребро, которое формирует кратчайший путь из истока в вершину, не включенную в SPT. То есть вершины заносятся в SPT в порядке их расстояния (по SPT-дереву) от начальной вершины. Этот метод называется алгоритмом Дейкстры (Dijkstra).

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

Лемма 21.2. Алгоритм Дейкстры решает задачу поиска кратчайших путей из одного истока в сетях с неотрицательными весами.

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

Таким же образом можно показать, что алгоритм Дейкстры решает задачу поиска кратчайших путей из истока в сток, если начать с истока и остановиться, когда сток покинет очередь с приоритетами. $$$\blacksquare$$$

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

На рис 21.10 показано развертывание SPT при вычислении по алгоритму Дейкстры, а на рис 21.11 показан рисунок большего ориентированного SPT-дерева. Хотя алгоритм Дейкстры отличается от алгоритма Прима для вычисления MST только выбором приоритета, SPT-деревья обладают характерными особенностями, отличающими их от MST. Их корень расположен в начальной вершине, а все ребра направлены в сторону от корня, тогда как в MST нет ни корня, ни направлений. При использовании алгоритма Прима мы иногда представляем MST-деревья как направленные деревья с корнем, но такие структуры все равно существенно отличаются от SPT (сравните ориентированное изображение на рис 20.9 с изображением на рис 21.11). Вообще-то природа SPT отчасти зависит и от выбора начальной вершины (см. рис 21.12).

Первоначальная реализация Дейкстры, которая годится для насыщенных графов, в точности соответствует алгоритму Прима для вычисления MST. Мы просто заменяем присваивание приоритета P в программе 20.6

  P = e->wt()
    (вес ребра) на
    P = wt[v] + e->wt()
      

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

Лемма 21.3. С помощью алгоритма Дейкстры можно найти любое SPT в насыщенной сети за линейное время.

Доказательство. Как и в случае алгоритма Прима для вычисления MST, после просмотра кода программы 20.6 очевидно, что время выполнения пропорционально V², т.е. линейно для насыщенных графов. $$$\blacksquare$$$

В случае разреженных графов возможно усовершенствование. Алгоритм Дейкстры можно рассматривать как обобщенный метод поиска на графе, который отличается от поиска в глубину (DFS), от поиска в ширину (BFS) и от алгоритма Прима для вычисления MST только правилом добавления ребер в дерево. Как и в , ребра, которые соединяют вершины дерева с вершинами, не включенными в дерево, содержатся в обобщенной очереди, называемой накопителем (fringe). Для реализации этой обобщенной очереди используется очередь с приоритетами и механизм изменения приоритетов, что позволяет объединить в одной реализации алгоритмы DFS, BFS и Прима (см. ). Эта схема поиска по приоритетам (PFS) включает и алгоритм Дейкстры. То есть замена оператора присваивания P в программе 20.7 на

  P = wt[v] + e->wt()
      

(расстояние от истока до конечной вершины ребра) дает реализацию алгоритма Дейкстры, которая удобна для обработки разреженных графов.

(рис 21.10) Алгоритм Дейкстры

Эта последовательность показывает построение алгоритмом Дейкстры остовного дерева кратчайших путей для сети с корнем в вершине 0. Жирными черными линиями на диаграммах сетей показаны ребра дерева, а жирными серыми - ребра в накопителе. Ориентированные изображения дерева в процессе его роста показаны в центре, а справа приведены списки ребер в накопителе. Вначале в дерево заносится вершина 0, а в накопитель - выходящие из него ребра 0-1 и 0-5 (рисунок вверху). На втором шаге мы переносим самое короткое из этих ребер, 0-5, из накопителя в дерево и проверяем ребра, исходящие из него:ребро 5-4 заносится в накопитель, а ребро 5-1 отбрасывается, поскольку оно не является частью более короткого пути из 0 в 1, чем известный путь 0-1 (второй рисунок сверху). Приоритет ребра 5-4 в накопителе равен длине представленного им пути 0-5-4 из вершины 0. На третьем шаге мы переносим ребро 0-1 из накопителя в дерево, заносим в на-копитель ребро 1-2 и отбрасываем 1-4 (третий сверху рисунок). На четвертом шаге мы переносим 5-4 из накопителя в дерево, заносим в накопитель 4-3 и заменяем 1-2 на 4-2, т.к. путь 0-5-4-2 короче, чем 0-1-2 (четвертый сверху). Мы держим в накопителе не более одного ребра, ведущего к каждой вершине, и выбираем из них то, которое лежит на кратчайшем пути от 0. Вычисление завершается переносом из накопителя в дерево ребра 4-2, а затем 4-3 (рисунок внизу).

(рис 21.11) Остовное дерево кратчайших путей

Здесь показана работа алгоритма Дейкстры для решения задачи поиска кратчайших путей из одного истока в случайном евклидовом орграфе с соседними связями (с двунаправленными ребрами, соответствующими каждой начерченной линии) - в том же стиле, что и рис 18.13, рис 18.24 и рис 20.9 Дерево поиска похоже на BFS, т.к. вершины обычно соединяются друг к другом короткими путями, но оно слегка более вытянутое и менее широкое, поскольку использование расстояний приводит к несколько более длинным путям, чем использование длин путей.

(рис 21.12) Примеры SPT-деревьев

Эти три примера демонстрируют рост SPT для трех различных положений истока: левое ребро (вверху), верхний левый угол (в центре), и центр (внизу).

Программа 21.1. Алгоритм Дейкстры (поиск по приоритетам)

Этот класс реализует АТД для поиска кратчайших путей из одного истока с линейным временем предварительной обработки, приватными данными, занимающими объем памяти, пропорциональный V, и функциями-членами с постояннным временем выполнения, которые возвращают длину кратчайшего пути и конечную вершину пути из истока в любую заданную вершину. Конструктор реализует алгоритм Дейкстры, используя для вычисления SPT очередь с приоритетами вершин (в порядке их удаления от истока). Интерфейс очереди с приоритетами - тот же, который используется в программе 20.7 и реализован в программе 20.10.

Конструктор выполняет обобщенный поиск на графе, который реализует другие алгоритмы PFS с другими назначениями приоритета P (см. текст). Оператор обнуления веса вершин дерева необходим для общей реализации PFS, но не для алгоритма Дейкстры, т.к. приоритеты вершин, добавляемых в SPT, являются неубывающими.

  template <class Graph, class Edge>
  class SPT
    { const Graph G;
      vector<double> wt;
      vector<Edge *> spt;
    public:
      SPT(const Graph G, int s) : G(G),
        spt(G.V()), wt(G.V(), G.V())
        { PQi<double> pQ(G.V(), wt);
          for (int v = 0; v < G.V(); v++) pQ.insert(v);
          wt[s] = 0.0; pQ.lower(s);
          while (!pQ.empty())
            { int v = pQ.getmin(); // wt[v] = 0.0;
              if (v != s  spt[v] == 0) return;
              typename Graph::adjIterator A(G, v);
              for (Edge* e = A.beg(); !A.end(); e = А.пх^))
                { int w = e->w();
                  double P = wt[v] + e->wt();
                  if (P < wt[w])
                    { wt[w] = P; pQ.lower(w); spt[w] = e; }
                }
            }
        }
    Edge *pathR(int v) const { return spt[v]; }
    double dist(int v) const { return wt[v]; }
    };
      

Программа 21.1 является альтернативной реализацией PFS для разреженных графов; она несколько проще программы 20.7 и непосредственно соответствует неформальному описанию алгоритма Дейкстры в начале этого раздела. Она отличается от программы 20.7 тем, что вначале все вершины сети заносятся в очередь с приоритетами, и те вершины в этой очереди, которые не находятся ни в дереве, ни в накопителе, помечаются сигнальными значениями (невидимые вершины с сигнальными значениями). А программа 20.7 содержит в очереди с приоритетами только вершины, достижимые из дерева через одно ребро. Хранение всех вершин в очереди упрощает код, хотя для некоторых графов может слегка ухудшить эффективность (см. упражнение 21.31).

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

Лемма 21.4. Для всех сетей и всех функций приоритетов можно вычислить остовное дерево с помощью PFS за время, пропорциональное времени, необходимому для выполнения V операций вставить, V операций удалить минимальное и E операций уменьшить ключ в очереди с приоритетами размером не более V.

Доказательство. Этот факт следует непосредственно из реализаций программ 20.7 и 21.1, основанных на очередях с приоритетами. Он дает слишком осторожную верхнюю границу, поскольку размер очереди с приоритетами часто намного меньше V, особенно в программе 20.7. $$$\blacksquare$$$

Лемма 21.5. С помощью реализации алгоритма Дейкстры на основе PFS, использующей пирамидальное дерево для реализации очереди с приоритетами, можно вычислить любое SPT за время, пропорциональное E lgV.

Доказательство. Этот результат является прямым следствием леммы 21.4. ¦ Лемма 21.6. Пусть задан граф с V вершинами, E ребрами и насыщенностью d = E/V. Если d < 2, то время выполнения алгоритма Дейкстры пропорционально VlgV Иначе реализация очереди с приоритетами на основе $$$\lceil E/V\rceil$$$ -арного пирамидального дерева позволяет улучшить время выполнения в худшем случае не менее чем в lg(E/V) раз - до $$$O(E lg_{d}V)$$$ (что линейно, если E равно по крайней мере $$$V^{l+e}$$$).

Доказательство. Этот результат непосредственно вытекает из леммы 20.12 и реализации очереди с приоритетами на основе многопутевых пирамидальных деревьев, которая рассмотрена после этой леммы. $$$\blacksquare$$$

В таблице 21.1 сведена информация о рассмотренных нами четырех основных алгоритмах PFS. Они отличаются только используемой функцией вычисления приоритета, но эта разница приводит к совершенно различным остовным деревьям (как и должно быть). Например, на рисунках, упоминаемых в таблице (и для многих других графов), дерево DFS является высоким и узким, дерево BFS - низким и широким; SPT похоже на дерево BFS, но не такое низкое и широкое, а MST - не низкое и широкое, но и не высокое и узкое.

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

Алгоритмы поиска по приоритетам

Алгоритм	Приоритет	Результат	Рисунок
DFS	Обращение прямого обхода	Дерево рекурсии	18.13
BFS	Прямой обход	SPT (ребра)	18.24
Прима	Вес ребра	MST	20.8
Дейкстры	Вес пути	SPT	21.9

Мы уже рассмотрели четыре различных реализации PFS. Первая - это классическая реализация обхода насыщенного графа, которая охватывает алгоритм Дейкстры и алгоритм Прима для вычисления MST (программа 20.6). Три другие реализации предназначены для разреженных графов и отличаются содержимым очереди с приоритетами:

Ребра из накопителя (программа 18.10)

Вершины из накопителя (программа 20.7)

Все вершины (программа 21.1).

Первая реализация имеет в основном познавательную ценность, вторая наиболее совершенна, а третья, пожалуй, самая простая из всех. На самом деле эта схема описывает 16 различных реализаций классических алгоритмов поиска на графах, а если учесть различные реализации очередей с приоритетами, то возможных вариантов будет еще больше. Это разнообразие сетей, алгоритмов и реализаций подчеркивает важность общих формулировок производительности в леммах 21.4-21.6, которые также сведены в таблицу 21.2.

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

Трудоемкость реализаций алгоритма Дейкстры

Алгоритм	Трудоемкость в худшем случае	Примечание
Классический	V2	Оптимален для насыщенных графов
PFS, полное пирамидальное дерево	E lgV	Самая простая реализация
PFS, пирамидальное дерево с накопителем	E lgV	Очень осторожная верхняя граница
PFS, пирамидальное d-дерево	$$$E lg-{d}V$$$	Линеен, если граф не слишком разрежен

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

Название алгоритм Дейкстры обычно используется для обозначения как абстрактного метода построения SPT пошаговым добавлением вершин в порядке их расстояния от истока, так и его реализации в виде алгоритма со временем выполнения, пропорциональным V², для представления матрицей смежности, поскольку Дейкстра представил и то, и другое в своей статье, опубликованной в 1959 г. (а также показал, что этим методом можно вычислить и MST). Повышение производительности на разреженных графах связано с последующими усовершенствованиями в технологии АТД и реализациях очереди с приоритетами, которые не предназначены для задач поиска кратчайших путей. Более высокая производительность алгоритма Дейкстры - одно из наиболее важных свойств этой технологии (см. раздел ссылок). Как и в случае с MST, для указания конкретных сочетаний мы применяем термины вроде " реализация алгоритма Дейкстры на основе PFS с использованием пирамидальных d-деревьев " .

В было показано, что при использовании в невзвешенных неориентированных графах прямой нумерации для приоритетов очередь с приоритетами действует как очередь FIFO и приводит к поиску в ширину (BFS). Алгоритм Дейкстры дает другую реализацию BFS: когда все веса ребер равны 1, он посещает вершины в порядке нумерации ребер на кратчайшем пути к начальной вершине. В этом случае очередь с приоритетами действует не совсем так, как очередь FIFO, т.к. элементы с одинаковыми приоритетами не обязательно извлекаются из очереди в том порядке, в котором они были занесены в нее.

Каждая из этих реализаций помещает ребра SPT-дерева из вершины 0 в индексированный именами вершин вектор spt, а в индексированный именами вершин вектор wt - длины кратчайших путей в каждую вершину SPT, и содержит функции-члены, обеспечивающие клиентам доступ к этим данным. Как обычно, на основе этих первичных данных можно построить различные функции и классы обработки графов (см. упражнения 21.21-21.28).

Упражнения

21.19. Покажите в стиле рис 21.10 результат вычисления алгоритмом Дейкстры SPT для сети, определяемой в упражнении 21.1, с начальной вершиной 0.

21.20. Как найти второй кратчайший путь в сети из s в t ?

21.21. Напишите клиентскую функцию, которая использует объект SPT для поиска вершины, наиболее удаленной от заданной вершины s (вершина, кратчайший путь в которую из s является наиболее длинным).

21.22. Напишите клиентскую функцию, которая использует объект SPT для вычисления среднего значения длины кратчайших путей из заданной вершины в каждую из вершин, достижимых из нее.

21.23. Разработайте на основе программы 21.1 класс с функцией-членом path, которая возвращает значение типа vector из библиотеки STL, содержащее указатели на ребра кратчайшего пути, соединяющего s и t в направлении от s к t.

21.24. Напишите клиентскую функцию, которая использует класс из упражнения 21.23 для вывода кратчайших путей из заданной вершины в остальные вершины заданной сети.

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

21.26. Разработайте алгоритм поиска ребра, удаление которого вызывает максимальное возрастание длины кратчайшего пути из одной заданной вершины в другую в заданной сети.

21.27. Реализуйте класс, который использует объекты SPT для анализа чувствительности ребер сети по отношению к заданной паре вершин s и t. Вычислите такую матрицу размером V х V, что для каждого u и v элемент на пересечении строки u и столбца v равен 1, если в сети существует ребро u-v, увеличение веса которого не приводит к увеличению длины кратчайшего пути из s в t, и равен 0 в противном случае.

21.28. Реализуйте класс, который использует объекты SPT для поиска кратчайшего пути, соединяющего одно заданное множество вершин с другим заданным множеством вершин в заданной сети.

21.29. Воспользуйтесь решением из упражнения 21.28 для реализации клиентской функции, которая находит кратчайший путь от левого ребра к правому ребру в случайной решетчатой сети (см. упражнение 20.17).

21.30. Покажите, что MST неориентированного графа эквивалентно SPT-дереву критических ребер (bottleneck SPT) этого графа: для каждой пары вершин v и w оно дает соединяющий их путь, наиболее длинное ребро которого имеет минимально возможную длину.

21.31. Эмпирически сравните производительность двух версий алгоритма Дейкстры для разреженных графов, которые описаны в этом разделе (программа 21.1 и программа 20.7, с соответствующим определением приоритета), для различных сетей (см. упражнения 21.4-21.8). Воспользуйтесь реализацией очереди с приоритетами на основе стандартного пирамидального дерева.

21.32. Эмпирически найдите наилучшее значение d для реализации очереди с приоритетами в виде пирамидального d-дерева (см. программу 20.10) для каждой из трех рассмотренных реализаций алгоритма PFS (программы 18.10, 20.7 и 21.1) и для различных сетей (см. упражнения 21.4-21.8).

21.33. Эмпирически определите эффект использования реализации очереди с приоритетами на основе турнира индексного пирамидального дерева (см. упражнение 9.53) в программе 21.1 для различных сетей (см. упражнения 21.4-21.8).

21.34. Эмпирически проанализируйте высоту и среднюю длину пути в SPT для различных сетей (см. упражнения 21.4-21.8).

21.35. Разработайте класс для задачи поиска кратчайших путей из истока в сток, основанный на коде наподобие программы 21.1, но в котором вначале в очередь с приоритетами заносится и исток, и сток. При этом SPT-деревья растут из обеих вершин; ваша основная задача - решить, что делать при их встрече.

21.36. Опишите семейство графов с V вершинами и E ребрами, для которых время работы алгоритма Дейкстры достигает границы для худшего случая.

21.37. Разработайте приемлемый генератор случайных графов с V вершинами и E ребрами, для которых время работы PFS-реализации алгоритма Дейкстры с использованием пирамидального дерева суперлинейно.

21.38. Напишите клиентскую программу для выполнения динамической графической анимации работы алгоритма Дейкстры. Программа должна создавать изображения наподобие рис 21.11 (см. упражнения 17.56-17.60). Протестируйте программу на случайных евклидовых сетях (см. упражнение 21.9).

Кратчайшие пути между всеми парами вершин

В этом разделе мы рассмотрим два класса, решающие задачу поиска кратчайших путей для всех пар вершин. Алгоритмы, которые мы реализуем, непосредственно обобщают два базовых алгоритма, которые были рассмотрены в для задачи транзитивного замыкания. Первый метод заключается в выполнении алгоритма Дейкстры из каждой вершины для получения кратчайших путей из этой вершины во все остальные. Если реализовать очередь с приоритетами с помощью пирамидального дерева, то при таком подходе время выполнения в худшем случае будет пропорционально VE lgV, а использование d-арного пирамидального дерева позволяет улучшить эту границу для многих типов сетей до VE. Второй метод, который позволяет напрямую решить данную задачу за время, пропорциональное V³, является расширением алгоритма Уоршалла, и называется алгоритм Флойда (Floyd).

Оба класса реализуют интерфейс АТД абстрактных кратчайших путей для нахождения кратчайших расстояний и путей. Этот интерфейс, который показан в программе 21.2, является обобщением интерфейса абстрактного транзитивного замыкания взвешенного орграфа для выяснения связности в орграфах, который был изучен в . В реализациях обоих классов конструктор решает задачу поиска кратчайших путей для всех пар вершин и сохраняет результат в приватных членах данных. Эти данные используются функциями ответов на запросы, которые возвращают длину кратчайшего пути из одной заданной вершины в другую, а также первое или последнее ребро в пути. Основное назначение реализации такого АТД - его практическое использование для реализации алгоритмов поиска кратчайших путей для всех пар вершин.

Программа 21.3 представляет собой пример клиентской программы, которая вычисляет взвешенный диаметр (weighted diameter) сети с помощью интерфейса АТД для поиска всех кратчайших путей. Она просматривает все пары вершин и находит такую пару, для которой длина кратчайшего пути максимальна, а затем обходит путь, ребро за ребром. На рис 21.13 показан путь, вычисленный этой программой для нашей демонстрационной евклидовой сети.

Программа 21.2. АТД кратчайших путей для всех пар вершин

Все наши решения задачи поиска кратчайших путей для всех пар вершин имеют вид классов с конструктором и двумя функциями ответов на запросы. Первая функция, dist, возвращает длину кратчайшего пути из первого аргумента во второй, а вторая - одна из двух возможных функций вычисления пути: либо path, возвращающая указатель на первое ребро в кратчайшем пути, либо pathR, возвращающая указатель на последнее ребро в кратчайшем пути. Если такой путь не существует, то функция path возвращает 0, а результат dist не определен.

Мы используем функции path или pathR в зависимости от того, что удобнее для рассматриваемого алгоритма; возможно, на практике одну из них (или обе) следует поместить в интерфейс, а в реализациях использовать различные вспомогательные функции, как описано в разделе 21.1 и в упражнениях в конце этого раздела.

  template <class Graph, class Edge> class SPall
    { public:
      SPall(const Graph );
      Edge *path(int, int) const;
      Edge *pathR(int, int) const;
      double dist(int, int) const;
    };
      

Цель алгоритмов, представленных в этом разделе, состоит в обеспечении постоянного времени выполнения функций ответов на запросы. Обычно ожидается огромное количество таких запросов, поэтому лучше затратить значительно больше ресурсов на вычисление приватных членов данных и предварительную обработку в конструкторе, чтобы затем быстро отвечать на запросы. Оба рассматриваемых нами алгоритма требуют объем памяти для приватных членов данных, пропорциональный V².

(рис 21.13) Диаметр сети

Диаметр сети - это наибольший элемент в матрице всех кратчайших путей сети, т.е. длина наиболее длинного из кратчайших путей, показанного здесь для нашей демонстрационной евклидовой сети.

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

Если ожидается лишь несколько запросов, то можно обойтись без предварительной обработки, и просто выполнять для каждого запроса алгоритм для одного истока; однако в наиболее распространенных ситуациях нужны более совершенные алгоритмы (см. упражнения 21.48-21.50). Эта задача обобщает задачу, которой посвящена большая часть - поддержка быстрых запросов достижимости при ограничении на доступную память.

Первая рассматриваемая нами реализация функции АТД поиска кратчайших путей для всех пар вершин решает эту задачу, используя алгоритм Дейкстры для решения задачи с одним истоком для каждой вершины. C++ позволяет записать этот метод непосредственно (см. программу 21.4): для решения задачи с одним истоком для каждой вершины создается вектор объектов SPT. Этот метод обобщает метод на основе BFS для невзвешенных неориентированных графов, который был рассмотрен в . Он также похож на использование DFS в программе 19.4, где вычисляется транзитивное замыкание невзвешенного орграфа с началом в каждой вершине.

Программа 21.3. Вычисление взвешенного диаметра сети

Эта клиентская функция демонстрирует использование интерфейса из программы 21.2. Она находит самый длинный из кратчайших путей в данной сети, выводит путь и возвращает его вес (т.е. диаметр сети).

  template <class Graph, class Edge>
  double diameter(Graph G)
    { int vmax = 0, wmax = 0;
      allSP<Graph, Edge> all(G);
      for (int v = 0; v < G.V(); v++)
        for (int w = 0; w < G.V(); w++)
          if (all.path(v, w))
            if (all.dist(v, w) > all.dist(vmax, wmax))
              { vmax = v; wmax = w; }
      int v = vmax; cout << v;
      while (v != wmax)
        { v = all.path(v, wmax)->w(); cout <<    << v; }
      return all.dist(vmax, wmax);
    }
      

Лемма 21.7. С помощью алгоритма Дейкстры можно найти все кратчайшие пути в сети с неотрицательными весами за время, пропорциональное $$$VE\log_{d}{V}$$$ , где d = 2, если E < 2 V и d = E/V в противном случае.

Доказательство. Непосредственно следует из леммы 21.6. $$$\blacksquare$$$

Как и в задачах о кратчайших путях из одного истока и задачах вычисления MST, эта граница слишком осторожна; для типичных графов время выполнения обычно равно VE.

Для сравнений этой реализации с другими полезно рассмотреть матрицы, неявно образованные структурой вектора векторов приватных членов данных. Векторы wt образуют как раз матрицу расстояний, рассмотренную в разделе 21.1: элемент этой матрицы на пересечении строки s и столбца t содержит длину кратчайшего пути из и 21.9, векторы spt образуют транспонированную матрицу путей: элемент на пересечении строки s и столбца t указывает на последнее ребро в кратчайшем пути из s в t.

Для насыщенных графов можно было бы использовать представление матрицей смежности и избежать вычисления обратного графа с помощью неявного транспонирования матрицы (поменяв местами индексы строк и столбцов), как в программе 19.7. Разработка такой реализации представляет собой интересное упражнение по программированию и приводит к компактной реализации (см. упражнение 21.43); однако другой подход, который будет рассмотрен ниже, допускает еще более компактную реализацию.

Рекомендуемый метод решения задачи поиска кратчайших путей для всех пар вершин в насыщенных графах был разработан Р. Флойдом (R. Floyd). Он точности повторяет метод Уоршалла, только вместо использования логической операции ИЛИ для отслеживания существования путей он проверяет расстояния для каждого ребра, чтобы определить, является ли это ребро частью нового, более короткого пути.

Программа 21.4. Алгоритм Дейкстры для поиска всех кратчайших путей

Этот класс использует алгоритм Дейкстры, чтобы построить SPT для каждой вершины. Это позволяет выполнять функции pathR и dist для любой пары вершин.

  #include "SPT.cc"
  template <class Graph, class Edge>
  class allSP
    { const Graph G;
      vector< SPT<Graph, Edge> *> A;
    public:
      allSP(const Graph G) : G(G), A(G.V())
        { for (int s = 0; s < G.V(); s++)
          A[s] = new SPT<Graph, Edge>(G, s);
        }
      Edge *pathR(int s, int t) const
        { return A[s]->pathR(t); }
      double dist(int s, int t) const
        { return A[s]->dist(t); }
    };
      

Как уже было сказано, в соответствующей абстрактной постановке алгоритмы Флойда и Уоршалла идентичны (см. и 21.1).

Программа 21.5 содержит функцию АТД поиска кратчайших путей для всех пар вершин, которая реализует алгоритм Флойда. В ней явно используются матрицы из раздела 21.1 как приватные члены данных: вектор векторов d размером V х V для матрицы расстояний и еще один вектор векторов p размером V х V для таблицы путей. Для каждой пары вершин s и t конструктор заносит в d[s][t] длину кратчайшего пути из s в t (которая возвращается функцией-членом dist), а в p[s][t] - индекс следующей вершины на кратчайшем пути из s в t (который возвращается функцией-членом path). Реализация основана на операции релаксации пути, рассмотренной в разделе 21.1.

Программа 21.5. Алгоритм Флойда для поиска всех кратчайших путей

Эта реализация интерфейса из программы 21.2 использует алгоритм Флойда - обобщение алгоритма Уоршалла (см. программу 19.3), которое находит кратчайшие пути между каждой парой точек, а не просто проверяет их существование.

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

  template <class Graph, class Edge>
  class allSP
    { const Graph G;
      vector <vector <Edge *> > p;
      vector <vector <double> > d;
    public:
      allSP(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++)
            for (int t = 0; t < V; t++)
              if (G.edge(s, t))
                { p[s][t] = G.edge(s, t);
                  d[s][t] = G.edge(s, t)->wt();
                }
          for (int s = 0; s < V; s++) d[s][s] = 0;
          for (int i = 0; i < V; i++)
            for (int s = 0; s < V; s++) if (p[s][i])
              for (int t = 0; t < V; t++) if (s != t)
                if (d[s][t] > d[s][i] + d[i][t])
                  { p[s][t] = p[s][i];
                    d[s][t] = d[s][i] + d[i][t];
                  }
        }
      Edge *path(int s, int t) const
        { return p[s][t]; }
      double dist(int s, int t) const
        { return d[s][t]; }
    };
      

Лемма 21.8. С помощью алгоритма Флойда можно найти все кратчайшие пути в сети за время, пропорциональное V³.

Доказательство. Время выполнения очевидно из структуры кода. Доказательство корректности алгоритма мы проведем по индукции точно так же, как для алгоритма Уоршалла. i-я итерация цикла вычисляет кратчайший путь в сети из s в t, который не содержит вершин с индексами больше i (кроме, возможно, конечных вершин s и t). Полагая, что это утверждение истинно для i-ой итерации цикла, покажем, что оно истинно и для (i + 1)-ой итерации. Любой кратчайший путь из s в t, который не содержит вершин с индексами, большими i + 1, либо (1) является путем из s в t, который найден в предыдущей итерации цикла и по индуктивному предположению имееет длину d[s][t] и не содержит вершин с индексами больше i; либо (2) составлен из путей из s в i и из i в t, ни один из которых не содержит вершин с индексами больше i, и в этом случае внутренний цикл устанавливает d[s][t]. $$$\blacksquare$$$

На рис 21.14 показана подробная трасса выполнения алгоритма Флойда для нашей демонстрационной сети. Если преобразовать каждый пустой элемент в 0 (указание на отсутствие ребра), а каждый непустой элемент - в 1 (указание на наличие ребра), то эти матрицы описывают работу алгоритма Уоршалла точно так же, как на рис 19.15. В случае алгоритма Флойда непустые элементы не только указывают существование пути, но и дают информацию об известном кратчайшем пути. Элемент в матрице расстояний содержит длину известного кратчайшего пути, который соединяет вершины, соответствующие данной строке и столбцу; соответствующий элемент в матрице путей дает следующую вершину на этом пути. По мере заполнения матриц непустыми элементами алгоритм Уоршалла просто перепроверяет, соединяют ли новые пути пары вершин, которые уже соединены известными путями. В отличие от этого, алгоритм Флойда должен проверить (и при необходимости обновить) каждый новый путь, чтобы убедиться, что он приводит к более коротким путям.

Сравнивая оценки времени выполнения в худшем случае для алгоритмов Дейкстры и Флойда, можно получить тот же результат для алгоритмов поиска кратчайших путей для всех пар вершин, что и для соответствующих алгоритмов транзитивного замыкания в. Понятно, что для разреженных сетей более подходит выполнение алгоритма Дейкстры из каждой вершины, поскольку время работы близко к VE. По мере возрастания насыщенности графа с ним все более конкурирует алгоритм Флойда, который всегда требует времени, пропорционального V³ (см. упражнение 21.67); он широко используется ввиду простоты реализации.

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

Классические решения описанной задачи поиска кратчайших путей для всех пар вершин предполагают, что имеется объем памяти, достаточный для хранения матриц расстояний и путей. Огромные разреженные графы, матрицы , до сих пор является открытой задача сведения затрат памяти до величины, пропорциональной V, при сохранении поддержки линейного времени ответов на запросы длины кратчайших путей.

(рис 21.14) Алгоритм Флойда

Эта последовательность показывает построение матриц кратчайших путей для всех пар вершин с помощью алгоритма Флойда. Для i от 0 до 5 (сверху вниз), мы рассматриваем для всех s и t все пути из s в t, в которых нет промежуточных вершин, больших i (заштрихованные вершины). Вначале единственными такими путями являются ребра сети, поэтому матрица расстояний (в центре) представляет собой матрицу смежности графа, а в матрицу путей (справа) для каждогоребра s-t заносится p[s][t]= t. Для вершины 0 (вверху) алгоритм находит, что путь 3-0-1 короче сигнального значения, которое означает отсутствие ребра 3-1, и соответствующим образом обновляет матрицы. Это не делается для путей наподобие 3-0-5, который не короче известного пути 3-5. Далее алгоритм рассматривает пути, проходящие через 0 и 1 (второй ряд сверху) и находит новые более короткие пути 0-1-2, 0-1-4, 3-0-1-2, 3-0-1-4 и 5-1-2. В третьем ряду сверху показаны обновления, соответствующие более коротким путям через 0, 1, 2 и т.д.

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

Мы выяснили, что имеется аналогичная трудноразрешимая проблема даже для более простой задачи достижимости (где достаточно было за линейное время узнать, имеется ли вообще какой-либо путь, соединяющий данную пару вершин), поэтому нельзя ожидать простого решения задачи поиска кратчайших путей для всех пар вершин. Вообще-то количество различных кратчайших длин путей в общем случае пропорционально V² даже для разреженных графов. Эта величина в некотором смысле служит мерой объема информации, которую требуется обработать, и, возможно, указывает, что если существует ограничение на объем памяти, то следует ожидать большего времени обработки каждого запроса (см. упражнения 21.48-21.50).

Упражнения

21.39. Оцените с точностью до порядка наибольший размер (количество вершин) графа, который ваш компьютер и система программирования могут обработать за 10 секунд, если для вычисления кратчайших путей использовать алгоритм Флойда.

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

21.41. Покажите в стиле рис 21.9 результат применения алгоритма Дейкстры для вычисления всех кратчайших путей в сети, определенной в упражнении 21.1.

21.42. Покажите в стиле рис 21.14 результат применения алгоритма Флойда для вычисления всех кратчайших путей в сети, определенной в упражнении 21.1.

21.43. Объедините программу 20.6 с программой 21.4 для реализации интерфейса АТД поиска кратчайших путей для всех пар вершин (на основе алгоритма Дейкстры) в насыщенных сетях, который поддерживает вызовы функции path, но не вычисляет явно обратную сеть. Не определяйте отдельную функцию для решения задачи с одним истоком - поместите код из программы 20.6 непосредственно во внутренний цикл и храните результаты непосредственно в приватных членах данных d и p, как в программе 21.5.

21.44. Эмпирически сравните в стиле таблицы 20.2 алгоритм Дейкстры (программа 21.4 и упражнение 21.43) и алгоритм Флойда (программа 21.5) для различных сетей (см. упражнения 21.4-21.8).

21.45. Эмпирически определите, сколько раз алгоритмы Флойда и Дейкстры обновляют значения в матрице расстояний для различных сетей (см. упражнения 21.4-21.8).

21.46. Приведите матрицу, в которой элемент в строке s и столбце t равен количеству различных простых направленных путей, соединяющих s и t на рис 21.1.

21.47. Реализуйте класс, конструктор которого вычисляет матрицу количества путей, описанную в упражнении 21.46, чтобы общедоступная функция-член могла выдавать это количество за постоянное время.

21.48. Разработайте реализацию класса для абстрактного АТД поиска кратчайших путей для разреженных графов, в которой необходимый объем памяти сокращается до величин, пропорциональных V, а время запроса увеличивается до значений, пропорциональных V.

21.49. Разработайте реализацию абстрактного класса АТД поиска кратчайших путей для разреженных графов, которая использует объем памяти, существенно меньший O(V²), но поддерживает запросы за время, намного меньшее O(V). Указание. Вычислите все кратчайшие пути для подмножества вершин.

21.50. Разработайте реализацию абстрактного класса АТД поиска кратчайших путей для разреженных графов, которая использует объем памяти, существенно меньший O( V²), и поддерживает (с помощью рандомизации) запросы за линейное ожидаемое время.

21.51. Разработайте реализацию абстрактного класса АТД поиска кратчайших путей, в которой используется ленивый подход применения алгоритма Дейкстры: SPT-дерево (и связанный с ним вектор расстояний) для вершины s строится при первом запросе клиентом кратчайшего пути из s, а при последующих запросах выбирается готовая информация.

21.52. Измените АТД кратчайших путей и алгоритм Дейкстры, чтобы вычислять кратчайшие путей в сетях, в которых веса имеют и вершины, и ребра. Не переделывайте представление графа (метод описан в упражнении 21.4), а измените код.

21.53. Постройте небольшую модель авиамаршрутов и времен перелета - возможно, на основе ваших путешествий. Воспользуйтесь решением упражнения 21.52 для вычисления наиболее быстрого пути от одного из пунктов к другому. Затем протестируйте полученную программу на реальных данных (см. упражнение 21.5).

Кратчайшие пути в ациклических сетях

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

Решают задачу для одного истока за линейное время.

Решают задачу для всех пар вершин за время, пропорциональное VE.

Решают другие задачи, например, поиск наиболее длинных путей.

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

Поскольку в ациклических сетях нет циклов вообще, то нет и отрицательных циклов, поэтому отрицательные веса не вызывают трудностей в задачах поиска кратчайших путей на DAG-графах. Соответственно, в материале этого раздела мы не накладываем ограничения на значения весов ребер.

Есть одно замечание, касающееся терминологии: ориентированные графы с весами на ребрах и без циклов можно называть либо взвешенными DAG, либо ациклическими сетями.

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

Четыре базовых концепции из , которые позволили получить эффективные алгоритмы для невзвешенных DAG-графов, оказываются даже более эффективными для взвешенных DAG:

Использование DFS для решения задачи с одним истоком.

Использование очереди истоков для решения задачи с одним истоком.

Вызов любого метода один раз для каждой вершины при решении задачи для всех пар вершин.

Использование одного DFS (с динамическим программированием) при решении задачи для всех пар вершин.

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

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

Кратчайшие пути из нескольких истоков. При заданном наборе начальных вершин для каждой из остальных вершин w нужно найти самый короткий путь среди всех кратчайших путей из каждой начальной вершины до w.

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

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

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

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

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

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

  #include "dagTS.cc"
  template <class Graph, class Edge>
  class LPTdag
    {
      const Graph G;
      vector<double> wt;
      vector<Edge *> lpt;
    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]; }
    } ;
      

(рис 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.

Лемма 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. $$$\blacksquare$$$

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

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

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

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

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

Программа 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][i]; 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.10. Задачу поиска кратчайших путей для всех пар вершин в ациклических сетях можно решить с помощью одного поиска в глубину за время, пропорциональное VE.

Доказательство. Это утверждение вытекает непосредственно из стратегии решения задачи с одним истоком для каждой вершины (см. упражнение 21.65). Его можно также доказать методом индукции из программы 21.7. После рекурсивных вызовов для вершины v мы знаем, что вычислены все кратчайшие пути для каждой вершины из списка смежности v - поэтому мы можем найти кратчайшие пути из v в каждую вершину, проверив все ребра, инцидентные v. Для каждого ребра выполняется Vшагов релаксации, а в сумме получается VE шагов релаксации. $$$\blacksquare$$$

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

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

(рис 21.16) Кратчайшие пути в ациклической сети

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

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

(рис 21.17) Все наиболее длинные пути в ациклической сети

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

Упражнения

21.54. Приведите решения задач поиска кратчайших и наиболее длинных путей с несколькими истоками для сети, определенной в упражнении 21.1, с обращенными направлениями ребер 2-3 и 1-0.

21.55. Измените программу 21.6, чтобы она решала задачу поиска кратчайших путей с несколькими истоками для ациклических сетей.

21.56. Реализуйте класс с тем же интерфейсом, что и в программе 21.6, на основе кода топологической сортировки с очередью истоков из программы 19.8, который выполняет операцию релаксации для каждой вершины сразу после извлечения этой вершины из очереди истоков.

21.57. Определите АТД для операции релаксации, напишите его реализацию и измените программу 21.6 так, чтобы полученный АТД можно было использовать аналогично программе 21.6 для решения задачи о кратчайших путях с несколькими истоками, задачи о наиболее длинных путях с несколькими истоками и других задач, просто измененяя реализацию операции релаксации.

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

21.59. Определите свойства релаксации, чтобы изменить доказательство леммы 21.9 для абстрактной версии программы 21.6 (наподобие описанной в упражнении 21.57).

21.60. Продемонстрируйте в стиле рис 21.16 вычисление матриц кратчайших путей для всех пар вершин в сети, определенной в упражнении 21.54, с помощью программы 21.7.

о 21.61. Приведите верхнюю границу количества весов ребер, просмотренных в программе 21.7, в виде функции базовых структурных свойств сети. Напишите программу вычисления этой функции и воспользуйтесь ей для оценки точности границы ).

21.62. Напишите основанное на DFS решение задачи о кратчайших путях с несколькими истоками для ациклических сетей. Будет ли это решение правильно работать при наличии отрицательных весов ребер? Обоснуйте свой ответ.

21.63. Расширьте решение упражнения 21.62, чтобы получить реализацию интерфейса АТД кратчайших путей для всех пар вершин для ациклических сетей, которая формирует матрицы всех путей и всех расстояний за время, пропорциональное VE.

21.64. Продемонстрируйте в стиле рис 21.9 вычисление всех кратчайших путей в сети, определенной в упражнении 21.54, с помощью метода на основе DFS из упражнения 21.63.

21.65. Измените программу 21.6, чтобы она решала задачу поиска кратчайших путей из одного истока в ациклических сетях, а затем используйте ее для разработки реализации интерфейса АТД кратчайших путей для всех пар вершин в ациклических сетях, который формирует матрицы всех путей и всех расстояний за время, пропорциональное VE.

21.66. Выполните упражнение 21.61 для реализации АТД кратчайших путей для всех пар вершин на основе DFS (упражнение 21.63) и на основе топологической сортировки (упражнение 21.65). Какие выводы можно сделать, сравнивая трудоемкости этих трех методов?

21.67. Эмпирически сравните в стиле таблицы 20.2 три реализации класса для задачи поиска кратчайших путей для всех пар вершин, описанные в этом разделе (см. программу 21.7, упражнение 21.63 и упражнение 21.65), для различных ациклических сетей (добавьте нужные веса в моделях из ).

Евклидовы сети

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

Эти сети обладают двумя важными свойствами, которые не обязательно присущи весам ребер в общем случае. Во-первых, расстояния удовлетворяют неравенству треугольника: расстояние от s до d никогда не больше, чем расстояние от s до x плюс расстояние от x до d. Во-вторых, координаты вершин дают нижнюю границу длины пути: не существует пути из s в d, который был бы короче расстояния между s и d по прямой. Алгоритм поиска кратчайших путей для задачи с одним истоком и стоком, который мы рассмотрим в этом разделе, использует эти два свойства для повышения его эффективности.

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

Основная идея проста: поиск по приоритетам предоставляет общий механизм для поиска путей в графах. С помощью алгоритма Дейкстры мы рассматриваем пути в порядке увеличения их расстояния от начальной вершины. Это упорядочение гарантирует, что по достижении стока будут просмотрены все более короткие пути в графе, ни один из которых не привел в сток. Но в евклидовом графе имеется дополнительная информация: если мы ищем путь из истока s в сток d и встречаем третью вершину v, то мы знаем, что нам не только необходимо учесть путь, найденный из s в v, но и что лучшее, что можно сделать при проходе из v в d - это сначала пройти по ребру ). Поиск по приоритетам позволяет легко учесть эту дополнительную информацию для повышения эффективности вычислений. Мы используем стандартный алгоритм, но в качестве приоритета для каждого ребра v-w принимаем сумму следующих трех величин: длина известного пути из s в v, вес ребра v-w, и расстояние от w до t. Если всегда выбирать ребро с наименьшей такой величиной, то по достижении вершины t мы будем уверены, что в данном графе не существует более короткого пути из s в t. Кроме того, в типичных сетях мы приходим к этому заключению после выполнения гораздо меньшего объема работы, чем при использовании алгоритма Дейкстры.

(рис 21.18) Релаксация ребра (евклидова)

Вычисляя кратчайшие пути в евклидовом графе, в операции релаксации можно учитывать расстояния до конечной вершины. В данном примере можно сделать вывод, что показанный путь из s в v с добавленным ребром v-w не может привести к более короткому пути из s в d, чем уже найденный, т.к. длина любого такого пути должна быть не меньше длины пути из s в v плюс длина v-w и плюс расстояние от w до d по прямой, что больше длины известного пути из s в d. Подобные проверки могут существенно уменьшить количество рассматриваемых путей.

Для реализации данного подхода мы используем стандартную алгоритма Дейкстры на основе PFS (см. программу 21.1, поскольку евклидовы графы обычно разрежены, а также упражнение 21.73) с двумя изменениями. Во-первых, вместо обнуления элементов wt[s] в начале поиска они заполняются величинами distance(s, d), где distance() - функция, возвращающая расстояние между двумя вершинами. Во-вторых, мы определяем приоритет P как функцию

  (wt[v] + e->wt() + distance(w, d) - distance(v, d))
      

вместо функции (wt[v] + e->wt0), которая использовалась в программе 21.1 (вспомните, что v и S - это локальные переменные, в которые заносятся, соответственно, величины e->v() и e->w()). Эти изменения, которые мы будем называть евклидовой эвристикой (Euclidean heuristic), сохраняют неизменным свойство, что величина wt[v] - distance(v, d) является длиной кратчайшего пути в сети из s в v для каждой вершины v (следовательно, wt[v] содержит нижнюю границу длины самого короткого из всех возможных путей из s в d через v). Величина wt[w] вычисляется добавлением к этой величине веса ребра (расстояние до w) плюс расстояние от w до стока d.

Лемма 21.11. Поиск по приоритетам с евклидовой эвристикой решает задачу кратчайших путей из истока в сток в евклидовых графах.

Доказательство. Здесь применимо доказательство леммы 21.2. В момент включения вершины x в дерево добавление расстояния между x и d к приоритету не влияет на то, что путь в дереве из s в x является кратчайшим путем в графе из s в x, поскольку к длине всех путей, ведущих в x, добавляется одна и та же величина.

Когда вершина d включена в дерево, мы знаем, что никакой другой путь из s в d не короче, чем путь по дереву, т.к. любой такой путь должен состоять из некоторого пути в дереве, за которым следует ребро, ведущее в некоторую вершину w вне дерева, а в конце находится путь из w в d (длина которого не может быть короче расстояния между w и d). Однако по построению мы знаем, что длина пути из s в w плюс расстояние от w до d не меньше длины пути по дереву из s в d. $$$\blacksquare$$$

В разделе 21.6 мы обсудим другой простой способ реализации евклидовой эвристики. Сначала мы перебираем все ребра графа, изменяя веса ребер: для каждого ребра v-w мы добавляем к весу величину distance(w, d) -distance(v, d). Затем выполняем стандартный алгоритм поиска кратчайшего пути, начиная с s (элемент wt[s] содержит значение distance(s,d)), и останавливаемся по достижении d. Этот метод в вычислительном отношении эквивалентен уже описанному методу (который вообще-то при своей работе вычисляет те же веса) и является конкретным примером базовой операции, которая называется перевзве-шивание (reweighting) сети. Перевзвешивание играет важную роль при решении задач поиска кратчайших путей с отрицательными весами; мы обсудим его подробно в разделе 21.6.

(рис 21.19) Кратчайший путь в евклидовом графе

Во время поиска кратчайшего пути в конечную вершину можно ограничить поиск вершинами внутри относительно небольшого эллипса вокруг пути, как показано в этих трех примерах, на которых изображены SPT-поддеревья для примеров с рис 21.12.

Евклидова эвристика влияет на эффективность, но не на правильность алгоритма Дейкстры для вычисления кратчайших путей из истока в сток. Как было сказано в доказательстве леммы 21.2, применение стандартного алгоритма для решения задачи с одним истоком и стоком означает построение SPT, в котором все вершины ближе к началу, чем сток d. При использовании евклидовой эвристики SPT содержит только те вершины, для которых длина пути из s плюс расстояние до d меньше длины кратчайшего пути из показано действие евклидовой эвристики на нашем демонстрационном графе, где выигрыш существенен. Мы называем этот метод эвристикой, поскольку выигрыш не гарантирован: всегда возможен случай, когда имеется единственный длинный путь, который может уйти произвольно далеко в сторону от истока и лишь затем направиться к стоку (см. упражнение 21.80).

На рис 21.20 наглядно демонстрируется геометрический смысл евклидовой эвристики: если длина кратчайшего пути из s в d равна z, то вершины, просматриваемые этим алгоритмом, лежат приблизительно внутри эллипса, определяемого как геометрическое место точек х, для которых расстояние от s до x плюс расстояние от х до d равно z. Для типичных евклидовых графов ожидаемое количество вершин в этом эллипсе намного меньше, чем количество вершин в круге радиуса z с центром в истоке (которые просматриваются алгоритмом Дейкстры).

(рис 21.20) Границы трудоемкости евклидовой эвристики

При продвижении к конечной вершине во время поиска кратчайшего пути можно ограничиться вершинами внутри эллипса, описанного вокруг пути, вместо круга с центром в истоке s, как в алгоритме Дейкстры. Радиус круга и форма эллипса определяются длиной кратчайшего пути.

Точный анализ получаемой экономии - трудная аналитическая задача, которая зависит от вида как множества случайных точек, так и случайных графов (см. раздел ссылок). В типичных ситуациях мы ожидаем, что если стандартный алгоритм при вычислении кратчайшего пути из истока в сток рассматривает X вершин, то евклидова эвристика сократит трудоемкость до величины, пропорциональной $$$\sqrt{X}$$$ , и тогда ожидаемое время выполнения будет пропорционально V для насыщенных графов и $$$\sqrt{V}$$$ для разреженных. Этот пример показывает, что трудность разработки подходящей модели или анализа связанных с ней алгоритмов не должна удерживать нас от использования значительного выигрыша, который возможен во многих приложениях, особенно если реализация тривиальна.

Доказательство леммы 21.11 применимо к любой функции, которая дает нижнюю границу расстояния от каждой вершины до d. Существуют ли другие функции, для которых алгоритм будет рассматривать еще меньше вершин, чем евклидова эвристики? Данный вопрос изучался в общей постановке применительно к широкому классу алгоритмов комбинаторного поиска. Вообще-то евклидова эвристика является одним из вариантов алгоритма, называемого A* (произносится " эй-стар " ). Эта теория утверждает, что оптимальной будет функция, которая дает наилучшую возможную нижнюю границу; другими словами, чем лучше эта граничная функция, тем более эффективен поиск. В данном случае оптимальность A* говорит о том, что евклидова эвристика наверняка просмотрит не больше вершин, чем алгоритм Дейкстры (который представляет собой A* с нулевой нижней границей). Результаты аналитических исследований дают более точную информацию для конкретных моделей случайных сетей.

Свойства евклидовых сетей можно использовать и для облегчения создания абстрактных АТД поиска кратчайших путей, более эффективно реализующих компромисс между используемым временем и памятью, чем для сетей общего вида (см. упражнения 21.48-21.50). Такие алгоритмы важны в приложениях наподобие обработки географических карт, где возникают огромные разреженные сети. Например, предположим, что требуется разработать навигационную систему, определяющую кратчайшие пути на карте с миллионами дорог. Возможно, саму карту можно хранить непосредственно в небольшом бортовом компьютере, однако матрицы расстояний и путей зачастую слишком велики для этого (см. упражнения 21.39 и 21.40); поэтому алгоритмы поиска всех путей из раздела 21.3 не применимы. Алгоритм Дейкстры также может не обеспечить достаточно быстрых ответов для огромных карт. В упражнениях 21.77 и 21.78 рассматриваются стратегии рационального соотношения между объемом предварительной обработки и объемом памяти, которые обеспечивают быструю реакцию на запросы о кратчайших путях из истока в сток.

Упражнения

21.68. Найдите в инернете большой евклидов граф - возможно, карту с таблицей расстояний между пунктами, телефонную сеть со стоимостями переговоров или расписание авиарейсов с указанными стоимостями билетов.

21.69. Используя стратегии, описываемые в упражнениях 17.71-17.73, напишите программы, которые генерируют случайные евклидовы графы, соединяя вершины, расположенные на решетке $$$\sqrt{V}\times \sqrt{V}$$$.

21.70. Покажите, что частичное SPT, вычисленное евклидовой эвристикой, не зависит от значения, которое вначале заносится в wt[s]. Объясните, как вычислять длины кратчайших путей из начального значения.

2l.71. Покажите в стиле рис 21.10 результат применения евклидовой эвристики для вычисления кратчайшего пути из 0 в 6 в сети из упражнения 21.1.

21.72. Опишите, что произойдет, если функция distance(s, t), используемая в евклидовой эвристике, возвращает фактическую длину кратчайшего пути из s в t для всех пар вершин.

21.73. Разработайте реализацию класса для поиска кратчайших путей в насыщенных евклидовых графах, основанную на представлении графа, которое поддерживает функцию edge и реализацию алгоритма Дейкстры (программа 20.6 с соответствующей функцией вычисления приоритета).

21.74. Эмпирически проверьте эффективность евклидовой эвристики поиска кратчайших путей для различных евклидовых сетей (см. упражнения 21.9, 21.68, 21.69 и 21.80). Для каждого графа сгенерируйте V/10 случайных пар вершин и выведите таблицу со следующими величинами: среднее расстояние между вершинами; средняя длина кратчайшего пути между вершинами; среднее отношение количества вершин, просматриваемых евклидовой эвристикой, к количеству вершин, просматриваемых алгоритмом Дейкстры; и среднее отношение площади эллипса, соответствующего евклидовой эвристике, к площади круга, соответствующего алгоритму Дейкстры.

21.75. Разработайте реализацию класса для задачи поиска кратчайших путей из истока в сток на евклидовых графах, которая основывается на двунаправленном поиске, описанном в упражнении 21.35.

21.76. Воспользуйтесь геометрической интерпретацией для оценки отношения количества вершин в SPT, создаваемом алгоритмом Дейкстры для задачи с истоком и стоком, к количеству вершин в SPT, создаваемом двунаправленной реализацией из упражнения 21.75.

21.77. Разработайте реализацию класса для поиска кратчайших путей в евклидовых графах, которая выполняет в конструкторе следующий шаг предварительной обработки: накладывает на район карты сетку $$$W \times W$$$, а затем при помощи алгоритма Флойда поиска кратчайших путей для всех пар вершин вычисляет матрицу $$$W^{2} \times W^{2}$$$, элемент которой на пересечении строки i и столбца j содержит длину кратчайшего пути, соединяющего любую вершину из квадрата сетки i с любой вершиной из квадрата j. Затем используйте эти длины кратчайших путей в качестве нижних границ для усовершенствования евклидовой эвристики. Проведите эксперименты для нескольких различных значений W, которые дают небольшое ожидаемое количество вершин в квадрате решетки.

21.78. Разработайте реализацию АТД поиска кратчайших путей для всех пар вершин в евклидовых графах, которая объединяет идеи, изложенные в упражнениях 21.75 и 21.77.

21.79. Эмпирически сравните эффективность эвристик, описанных в упражнениях 21.75-21.78, для различных евклидовых сетей (см. упражнения 21.9, 21.68, 21.69 и 21.80).

21.80. Расширьте эмпирические исследования, включив в них евклидовы графы, которые получаются удалением всех вершин и ребер из круга радиуса r в центре, для r = 0.1, 0.2, 0.3 и 0.4. (Эти графы обеспечивают серьезную проверку евклидовой эвристики.)

21.81. Приведите прямую реализацию алгоритма Флойда, которая позволит реализовать АТД сети для неявных евклидовых графов, определяемых N точками на плоскости с ребрами, которые соединяют друг с другом точки на расстоянии не больше d. Не представляйте эти графы явным образом; вместо этого для заданных двух вершин вычислите расстояние между ними, чтобы определить, существует ли ребро, и если да, то чему равна его длина.

21.82. Разработайте реализацию, описанную в упражнении 21.81, которая строит граф с соседними связями, а затем применяет к каждой вершине алгоритм Дейкстры (см. программу 21.1).

21.83. Эмпирически сравните время выполнения и объем памяти, необходимые для алгоритмов из упражнений 21.81 и 21.82, для d = 0.1, 0.2, 0.3 и 0.4.

21.84. Напишите клиентскую программу, которая выполняет динамическую графическую анимацию работы евклидовой эвристики. Программа должна создать изображения наподобие рис 21.19 (см. упражнение 21.38). Протестируйте программу на различных евклидовых сетях (см. упражнения 21.9, 21.68, 21.69 и 21.80).

Сведение

Задачи о кратчайших путях - особенно общий случай, где допустимы отрицательные веса (тема раздела 21.7) - представляют обобщенную математическую модель, которую можно использовать для решения множества других задач, с виду не имеющих отношения к обработке графов. Эта модель является первой среди ряда таких общих моделей, с которыми мы еще встретимся. По мере перехода к более трудным задачам и все более общим моделям возникает одна из сложностей - точное описание взаимосвязей между различными задачами. Для каждой новой задачи требуется ответить на вопрос: возможно ли ее простое решение с помощью преобразования в задачу, которую мы уже умеем решать? Станет ли решение более легким, если наложить на задачу некоторые ограничения? Чтобы отвечать на подобные вопросы, в этом разделе мы ненадолго отклонимся от темы и обсудим термины, используемые для описания таких видов взаимосвязи между задачами.

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

Отложим до части VIII строгое определение того, что означают слова " использовать" один алгоритм для " разработки " другого. Для большинства приложений достаточно следующего простого приема. Мы показываем, что A сводится к B, если покажем возможность решения любого экземпляра задачи A за три шага:

Преобразование ее к задаче B.

Решение полученной задачи B.

Преобразование решения задачи B в решение задачи A.

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

Лемма 21.12. Задача транзитивного замыкания сводится к задаче поиска кратчайших путей для всех пар вершин с неотрицательными весами.

Доказательство. Мы уже отмечали прямую связь между алгоритмами Уоршалла и Флойда. Возможен другой способ установить их взаимосвязь в настоящем контексте: представьте, что требуется вычислить транзитивное замыкание орграфов с помощью библиотечной функции поиска всех кратчайших путей в сетях. Для этого мы добавим в орграф петли, если их нет, а затем построим сеть непосредственно из матрицы смежности орграфа с произвольным весом (скажем, 0.1), соответствующим каждому единичному элементу и сигнальным весом, соответствующим каждому нулевому элементу. Затем вызовем функцию поиска кратчайших путей для всех пар вершин. Из вычисленной матрицы кратчайших путей для всех пар вершин можно легко найти транзитивное замыкание: для любых двух заданных вершин u и v путь в орграфе из u в v существует тогда и только тогда, когда длина пути в сети из u в v не равна нулю (см. рис 21.21). $$$\blacksquare$$$

(рис 21.21) Сведение транзитивного замыкания

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

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

Лемма 21.13. В сетях без ограничений на веса ребер задачи поиска наиболее длинного пути и кратчайшего пути (из одного истока или для всех пар вершин) эквивалентны.

Доказательство. Для заданной задачи поиска кратчайшего пути изменим знаки всех весов. Наиболее длинный (т.е. с наибольшим весом) путь в модифицированной сети является кратчайшим путем в исходной сети. Аналогичное рассуждение показывает, что задача поиска кратчайшего пути сводится к задаче поиска наиболее длинного пути. $$$\blacksquare$$$

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

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

По существу, концепция сведения описывает процесс использования одного АТД для реализации другого, как это обычно делается современными системными программистами. Если две задачи эквивалентны, и мы умеем эффективно решать какую-то из них, мы можем эффективно решить и другую. Мы часто находим простые взаимно однозначные соответствия, как, например, в лемме 21.13, где показана эквивалентность двух задач. В этом случае, даже до обсуждения способа решения каждой из задач, важно знать, что если удастся найти эффективное решение одной задачи, то его можно применить и для решения другой. Еще один пример был приведен в : когда мы рассматривали задачу определения, содержит ли граф нечетный цикл, мы установили, что эта задача эквивалентна определению, можно ли раскрасить граф двумя цветами.

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

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

Естественно, трудоемкость преобразований обычно не должна быть больше трудоемкости решения. Однако во многих случаях сведение можно использовать даже при доминировании стоимости преобразования. Одно из наиболее важных применений сведения заключается в преобразовании к уже изученной задаче, для которой известно эффективное решение, что обеспечивает эффективные решения таких задач, которые иначе считались бы трудноразрешимыми. Сведение A к B, даже если это преобразование обойдется намного дороже, чем решение B, может дать намного более эффективный алгоритм решения, чем созданные другими способами. Существует множество различных вариантов. Возможно, нам более важна ожидаемая трудоемкость, а не трудоемкость в худшем случае. Возможно, для решения A потребуется решить две задачи, B и C. Может быть, потребуется многократно решить задачу B. Мы отложим дальнейшее обсуждение таких вариаций до части 8, поскольку все примеры, которые мы будем рассматривать до этого, не сложнее только что рассмотренных.

В частности, когда мы решаем задачу A, упрощая другую задачу B, мы знаем, что A сводится к B, но не обязательно наоборот. Например, выборка сводится к сортировке, поскольку наименьший k-й элемент в файле можно найти, отсортировав файл и затем перейдя по индексу (или последовательно) в его k-ю позицию; однако отсюда, конечно же, не следует, что сортировка сводится к выборке. В данном контексте и задача поиска кратчайших путей для взвешенного DAG, и задача поиска кратчайших путей для сетей с положительными весами сводится к общей задаче вычисления кратчайших путей. Такое использование сведения соответствует естественному пониманию, что одна задача является более общим случаем, чем другая. Любой алгоритм сортировки решает любую задачу выборки и, если мы можем решить задачу поиска кратчайших путей в сетях общего вида, то, конечно, можно воспользоваться этим решением для сетей с различными ограничениями. Однако обратное утверждение не обязательно верно.

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

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

На рис 21.22 приведен пример задачи календарного планирования. Здесь используется естественное представление в виде сети, которое в данном случае послужит инструментом сведения. Этот вариант задачи является, возможно, наиболее простым из буквально сотен изученных вариантов, которые содержат другие характеристики работ и другие ограничения - например, назначение работам персонала или других ресурсов, других расходов, конечных сроков выполнения и т.п. В этом контексте описанный выше вариант обычно называется календарным планированием с ограничениями предшествования и неограниченным параллелизмом. Для краткости в дальнейшем мы будем применять термин календарное планирование.

Для упрощения разработки алгоритма, решающего задачу планирования работ, мы рассмотрим следующую задачу, которая представляет интерес и сама по себе.

(рис 21.22) Календарное планирование

В этой сети вершины представляют работы, которые требуется выполнить (с весами, указывающими необходимое время), а ребра - отношения предшествования между работами. Например, ребра из 7 в 8 и в 3 означают, что работа 7 должна быть завершена до начала работы 8 и работы 3. Каково минимальное время, необходимое для завершения всех работ?

Разностные ограничения. Нужно присвоить неотрицательные значения множеству переменных x0, ..., xn , которые минимизируют значение x_n, удовлетворяя множеству разностных ограничений на переменные, каждое из которых указывает, что разность между какими-то двумя переменными должна быть больше или равна заданной константе.

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

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

Линейное программирование. Нужно присвоить неотрицательные значения множеству переменных x0, ..., xn , которые минимизируют значение заданной линейной комбинации переменных при наличии множества ограничений на переменные, каждое из которых указывает, что заданная линейная комбинация переменных должна быть больше или равна некоторой заданной константе.

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

Лемма 21.14. Задача календарного планирования сводится к задаче разностных ограничений.

Доказательство. Для каждой работы добавим фиктивную работу и такое ограничение предшествования, что данная работа должна закончиться до начала фиктивной работы. Для этой задачи календарного планирования определим систему разностных неравенств, где каждой работе i соответствуют переменная x_i и ограничение, согласно которому работа j не может начаться до окончания работы i в соответствии с неравенством $$$x_{j} \geq x_{i}+c_{i}$$$, где c_i, - продолжительность работы i. Решение задачи разностных ограничений дает как раз решение задачи календарного планирования, при этом значение каждой переменной задает время начала соответствующей работы. $$$\blacksquare$$$

На рис 21.23 приведена система разностных неравенств, которая сформирована сведением задачи календарного планирования с рис 21.22. Практическое значение этого сведения состоит в том, что для решения задачи календарного планирования можно воспользоваться любым алгоритмом, позволяющим решать задачи разностных ограничений.

(рис 21.23) Разностные ограничения

Нахождение неотрицательных значений переменных, которые минимизируют значение x₁₀ с учетом данного множества неравенств, эквивалентно задаче календарного планирования работ, которая приведена на рис 21.22. Например, неравенство $$$x_{8} \geq x_{7}+0,32$$$ означает, что работа 8 не может начаться до завершения работы 7.

Полезно подумать, можно ли провести аналогичное построение в обратном направлении: если имеется алгоритм решения задачи календарного планирования, то можно ли воспользоваться им для решения задачи разностных ограничений? Ответ на этот вопрос таков: формулировка леммы 21.14 не означает, что задача разностных ограничений сводится к задаче календарного планирования, поскольку системы разностных неравенств, которые получаются из задачи календарного планирования, имеют свойство, которое не обязательно справедливо для каждой задачи разностных ограничений. А именно: если в двух неравенствах совпадают вторые переменные, то совпадают и константы.

Следовательно, алгоритм для календарного планирования работ непосредственно не позволяет решать системы разностных неравенств, если в них имеются два таких неравенства: $$$x_{i}-x_{j} \geq a$$$ и $$$x_{k}-x_{j} \geq b$$$, где $$$a\neq b$$$. При доказательстве возможности сведения следует иметь в виду ситуации, подобные следующей: в доказательстве, что A сводится к B, необходимо показать, что алгоритм решения задачи B позволяет решить любой вариант задачи A.

Константы в задачах разностных ограничений, создаваемые при доказательстве леммы 21.14, всегда неотрицательны. Этот факт имеет существенное значение.

Лемма 21.15. Задача разностных ограничений при положительных константах эквивалентна задаче поиска наиболее длинных путей из одного истока в ациклической сети.

Доказательство. Пусть задана система разностных неравенств. Построим сеть, где каждая переменная xt соответствует вершине i, а каждое неравенство $$$x_{i}-x_{j} \geq c$$$ соответствует ребру i-j веса с. Например, назначение каждому ребру в орграфе на рис 21.22 веса его начальной вершины дает сеть, соответствующую множеству разностных неравенств с рис. 21.23 рис 21.23. Добавим к сети фиктивную вершину с ребрами нулевого веса, направленными в каждую из остальных вершин. При наличии в сети цикла система разностных неравенств не имеет решения (поскольку из положительности весов следует, что значения переменных, соответствующих каждой вершине, строго уменьшаются при движении вдоль пути, и тогда наличие цикла означает, что некоторая переменная меньше себя самой), и остается сообщить об этом. Если же в сети нет циклов, мы решим задачу поиска наиболее длинных путей из одного истока - фиктивной вершины. Наиболее длинный путь существует для каждой вершины, т.к. сеть является ациклической (см. раздел 21.4). Присвоим каждой переменной длину наиболее длинного пути из фиктивной вершины в соответствующую вершину сети. Для каждой переменной существование этого пути означает, что значение такой переменной удовлетворяет ограничениям, но никакое меньшее значение ограничениям не удовлетворяет.

В отличие от доказательства леммы 21.14, данное доказательство можно расширить, чтобы показать эквивалентность двух задач, поскольку построение работает в обоих направлениях. Здесь нет ограничения, что два неравенства с одинаковыми вторыми переменными в неравенстве должны иметь одинаковые константы, и нет требования, что ребра, исходящие из любой заданной вершины в сети, должны иметь одинаковые веса. Для любой заданной ациклической сети с положительными весами такое же соответствие дает систему разностных ограничений с положительными константами, решение которой непосредственно дает решение задачи поиска наиболее длинных путей из одного истока в сети. Детали этого доказательства оставляем на самостоятельную проработку (см. упражнение 21.90). $$$\blacksquare$$$

Сеть на рис 21.22 демонстрирует это соответствие для нашей типовой задачи, а на рис 21.15 показано вычисление наиболее длинных путей в сети с помощью программы 21.6 (фиктивная исходная вершина неявно фигурирует в реализации). График выполнения работ, вычисленный этим способом, приведен на рис 21.24.

Программа 21.8 представляет собой реализацию, которая демонстрирует практическое применение данной теории. Она преобразовывает любую задачу календарного планирования в задачу поиска наиболее длинного пути в ациклических сетях, а затем использует программу 21.6 для ее решения.

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

(рис 21.24) График выполнения работ

Этот рисунок демонстрирует решение задачи календарного планирования с рис 21.22, полученное из соответствия между наиболее длинными путями во взвешенном DAG и календарным планированием. Длины наиболее длинных путей в массиве wt, вычисленном алгоритмом поиска наиболее длинных путей в программе 21.6 (см. рис 21.15), в точности равны моментам времени начала работ (правый столбец вверху). Работы 0 и 5 начинаются в момент 0.00 , работы 1, 7 и 9 - в момент 0.41, работы 4 и 6 - в момент 0.70 и т.д.

Определение 21.4. Экземпляр задачи, для которого не существует решение, называется неразрешимым (infeasible).

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

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

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

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

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

Программа 21.8. Календарное планирование

Эта реализация читает из стандартного ввода список работ с их длительностями, за которым следует список ограничений предшествования, а затем выводит в стандартный вывод список моментов начала работ, которые удовлетворяют данным ограничениям. Используя леммы 21.14 и 21.15, а также программу 21.6, она решает задачу календарного планирования сведением ее к задаче поиска наиболее длинных путей для ациклических сетей.

  #include "GRAPHbasic.cc"
  #include "GRAPHio.cc"
  #include "LPTdag.cc"
  typedef WeightedEdge EDGE;
  typedef DenseGRAPH<EDGE> GRAPH;
  int main(int argc, char *argv[])
    { int i, s, t, N = atoi(argv[1]);
      double duration[N];
      GRAPH G(N, true);
      for (int i = 0; i < N; i++)
        cin >> duration[i];
      while (cin >> s >> t)
        G.insert(new EDGE(s, t, duration[s]));
      LPTdag<GRAPH, EDGE> lpt(G);
      for (i = 0; i < N; i++)
        cout << i << " " << lpt.dist(i) << endl;
    }
      

Предположим, что в пример, представленный на рис 21.24, нужно добавить ограничение, состоящее в том, что работа 2 должна начаться не позже заданного количества единиц времени с после начала работы 4. Если с больше 0.53, то полученное расписание укладывается в заданные рамки, поскольку оно предписывает начать работу 2 в момент 1.23, что соответствует задержке на 0.53 после окончания работы 4 (которая начинается в момент 0.70). Если с меньше 0.53, то можно удовлетворить это ограничение, сдвинув начало работы 4 на более позднее время. Если работа 4 длится долго, то это изменение может увеличить время завершения всего графика. Хуже, если существуют другие ограничения на работу 4 , и мы не можем переместить время ее начала. Вообще-то бывают ограничения, которым не может удовлетворить ни одно расписание. Например, в нашем примере не удастся удовлетворить таким ограничениям, при которых работа 2 должна начаться раньше чем через d единиц времени после начала работы 6, для d меньшего 0.53, т.к. из ограничений, что работа 2 должна следовать за 8, а 8 за 6, следует, что работа 2 должна начаться позже, чем через 0.53 единицы времени после начала работы 6.

Если добавить в наш пример оба ограничения, рассмотренные в предыдущем абзаце, то, в зависимости от значений с и d, каждое ограничение повлияет на момент начала работы 4 в расписании, на время завершения всего графика, а также на то, существует ли выполнимый календарный график. Добавление дополнительных подобных ограничений увеличивает количество возможностей и превращает легкую задачу в трудную. Так что мы имеем все основания искать способ сведения этой задачи к некоторой известной задаче.

Лемма 21.16. Задача календарного планирования с конечными сроками сводится к задаче поиска кратчайших путей (с возможностью существования отрицательных весов).

Доказательство. Преобразуем ограничения предшествования в неравенства, используя то же сведение, что и описанное в свойстве 21.14. Для каждого ограничения конечного срока добавим неравенство $$$x_{i}-x_{j} \leq d_{j}$$$ , что эквивалентно $$$x_{j}-x_{i} \leq -d_{j}$$$ , где d_j - положительная константа. Преобразуем множество неравенств в сеть, применив то же сведение, что и описанное в лемме 21.15. Изменим знаки всех весов. Такое же построение, что и в доказательстве леммы 21.15, позволяет показать, что любое дерево кратчайших путей в сети с корнем в 0 будет соответствовать графику. $$$\blacksquare$$$

Это сведение подводит нас к вопросу о кратчайших путях с отрицательными весами. Оно утверждает, что если можно найти эффективное решение задачи поиска кратчайших путей с отрицательными весами, то можно найти эффективное решение задачи планирования работ с конечными сроками. (Опять-таки, соответствие в доказательстве леммы 21.16 не означает наличие обратного утверждения (см. упражнение 21.91).)

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

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

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

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

Лемма 21.17. Задача является NP-трудной, если существует эффективное сведение к ней любой NP-трудной задачи.

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

Теперь предположим, что имеется эффективное сведение NP-трудной задачи A к конкретной задаче B. Проведем доказательство от противного: если существует эффективный алгоритм для B, то мы могли бы воспользоваться им для решения с помощью сведения любого экземпляра задачи A за полиномиальное время (преобразуем данный экземпляр A в экземпляр B, решаем эту задачу, а затем преобразуем полученное решение). Однако не существует известного алгоритма, который гарантировал бы такое решение для A (поскольку A является NP-трудной), поэтому предположение о существовании алгоритма с полиномиальным временем для задачи B неверно, т.е. B также является NP-трудной задачей. $$$\blacksquare$$$

Эта методика является чрезвычайно важной, поскольку она позволяет показать, что огромное множество задач относятся к NP-трудным, предоставляя на выбор широкий круг задач, с помощью которых строились доказательства NP-трудности новой задачи. Например, в мы столкнулись с одной из классических NP-трудных задач - с задачей поиска гамильтонова пути, где нужно определить, существует ли простой путь, содержащий все вершины данного графа. Она была одной из первых задач, в отношении которой было показано, что она является NP-трудной (см. раздел ссылок). Ее нетрудно сформулировать в виде задачи поиска кратчайших путей, и поэтому из леммы 21.17 следует, что задача кратчайших путей относится к NP-трудным:

Лемма 21.18. В сетях, в которых веса ребер могут быть отрицательными, задачи поиска кратчайших путей являются NP-трудными.

Доказательство. Наше доказательство основано на сведении задачи о гамильтоновом пути к задаче о кратчайших путях. То есть мы покажем, что для решения задачи о гамильтоновом пути можно использовать любой алгоритм, позволяющий найти кратчайшие пути в сетях с отрицательными весами ребер. Для заданного неориентированного графа построим сеть с ребрами в обоих направлениях, соответствующими каждому ребру в графе, и присвоим каждому ребру вес -1. Кратчайший (простой) путь, начинающийся в любой вершине этой сети, имеет длину 1 - V тогда и только тогда, когда в графе существует гамильтонов путь. Обратите внимание, что эта сеть изобилует отрицательными циклами. Не только каждый цикл в графе соответствует отрицательному циклу в сети, но и каждое ребро в графе соответствует циклу с весом -2 в данной сети.

Из этого построения следует, что задача поиска кратчайших путей является NP-трудной, поскольку если бы мы могли разработать эффективный алгоритм для задачи поиска кратчайших путей в сетях, то мы имели бы эффективный алгоритм для задачи поиска гамильтонова пути в графах. $$$\blacksquare$$$

Если мы обнаруживаем, что данная задача является NP-трудной, естественно начать искать те варианты этой задачи, которые можно решить. Для задач поиска кратчайших путей мы имеем массу эффективных алгоритмов для ациклических сетей или для сетей, в которых веса ребер не являются отрицательными, и отсутствие хорошего решения для сетей, которые могут содержать циклы и отрицательные веса. Существуют ли какие-либо другие виды сетей, которые нас могут заинтересовать? Эта тема будет рассмотрена в разделе 21.7. Там, например, будет показано, что задача календарного планирования с конечными сроками сводится к варианту задачи поиска кратчайших путей, которую можно эффективно решить. Это обычная ситуация: при переходе ко все более трудным вычислительным задачам мы пытаемся выявить такие варианты данных задач, для которых мы надеемся найти решение.

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

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

В этой таблице приведены некоторые выводы из сведения задачи A к другой задаче B, с примерами, которые были рассмотрены в этом разделе. Глубокие выводы из случаев 9 и 10 ведут настолько далеко, что мы в общем случае предполагаем, что обосновать такие сведения невозможно (см. часть VIII). Сведение наиболее полезно в случаях 1, 6, 11 и 16 - для изучения нового алгоритма для A или обоснования нижней границы для B; 13-15 - для изучения новых алгоритмов для A; 12 - чтобы оценить сложность B.

Выводы из сведения

A	B	Вывод из сведения $$$A\Rightarrow B$$$	Пример
1 Простая	Простая	Новая нижняя граница B	Сортировка $$$\Rightarrow EMST$$$
2 Простая	Разрешимая	Нет	$$$TC\Rightarrow APSP(+)$$$
3 Простая	Трудноразрешимая	Нет	$$$SSSP(DAG)\Rightarrow SSSP(\pm)$$$
4 Простая	Решение не известно	Нет
5 Разрешимая	Простая	A простая
6 Разрешимая	Разрешимая	Новое решение A	$$$DC(+)\Rightarrow SSSP(DAG)$$$
7 Разрешимая	Трудноразрешимая	Нет
8 Разрешимая	Решение не известно	Нет
9 Трудноразрешимая	Простая	Глубокий
10 Трудноразрешимая	Разрешимая	Глубокий
11 Трудноразрешимая	Трудноразрешимая	Так же, как 1 или 6	$$$SSLP(\p)\Rightarrow SSSP(\pm)$$$
12 Трудноразрешимая	Решение не известно	B неразрешимая	$$$HP\Rightarrow SSSP(\pm)$$$
13 Решение не известно	Простая	A простая	$$$JS\Rightarrow SSSP(DAG)$$$
14 Решение не известно	Разрешимая	A разрешимая
15 Решение не известно	Трудноразрешимая	A разрешимая
16 Решение не известно	Решение не известно	Так же, как 1 или 6	$$$JSWD\Rightarrow SSSP(\pm)$$$

Обозначения:
EMST	минимальное евклидово остовное дерево
TC	транзитивное замыкание
APSP	кратчайшие пути для всех пар вершин
SSSP	кратчайшие пути из одного истока
SSLP	наиболее длинные пути из одного истока
(+)	(в сетях с неотрицательными весами)
(±)	(в сетях с весами, которые могут быть отрицательными)	(DAG)	(в ациклических сетях)
DC	разностные ограничения
HP	гамильтоновы пути
JS(WD)	планирование заданий (с конечными сроками)

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

Нижние границы. Если известно, что любой алгоритм для задачи A требует определенных ресурсов, и можно доказать, что A сводится к B, то мы знаем, что B имеет, по крайней мере, такие же требования к ресурсам, т.к. из существования лучшего алгоритма для B следовало бы существование лучшего алгоритма для A (если стоимость сведения меньше стоимости алгоритма B). То есть эффективность A равна нижней границе того, что можно получить в лучшем случае для B. Например, эта технология применялась в , чтобы показать, что вычисление транзитивного замыкания имеет такую же трудоемкость, как умножение логических матриц, и в - чтобы показать, что вычисление евклидова MST так же трудоемко, как сортировка.

Трудноразрешимость. В частности, можно доказать, что некоторая задача трудноразрешима, показав, что к ней сводится другая трудноразрешимая задача. Например, из леммы 21.18 следует, что задача поиска кратчайших путей трудноразрешима, поскольку к ней сводится задача поиска гамильтонова пути, которая является трудноразрешимой.

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

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

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

Сведение - это современная концепция, которая по сути аналогична математическому программированию и является основой нашего понимания трудоемкости вычислений для широкого круга приложений.

Упражнения

21.85. При помощи сведения, описанного в лемме 21.12, разработайте реализацию транзитивного замыкания (с тем же интерфейсом, что и в программах 19.3 и 19.4), которая использует АТД поиска кратчайших путей для всех пар вершин из раздела 21.3.

21.86. Покажите, что задача вычисления количества сильных компонентов в орграфе сводится к задаче поиска кратчайших путей для всех пар вершин с неотрицательными весами.

21.87. Приведите задачи разностных ограничений и кратчайших путей, которые соответствуют (аналогично построению лемм 21.14 и 21.15) задаче календарного планирования, где работы 0-7 имеют, соответственно, длины

0.40.20.30.40.20.50.1

и ограничения

5-14-66-03-26-16-2.

21.88. Приведите решение задачи календарного планирования из упражнения 21.87.

21.89. Предположим, что работы из упражнения 21.87 имеют дополнительные ограничения: работа 1 должна начаться до окончания работы 6, а работа 2 должна начаться до окончания работы 4 . Приведите задачу поиска кратчайших путей, к которой сводится эта задача, воспользовавшись построением из доказательства леммы 21.16.

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

21.91. Объясните, почему соответствие в доказательстве леммы 21.16 нельзя расширить для доказательства того, что задача поиска кратчайших путей сводится к задаче календарного планирования с конечными сроками.

21.92. Усовершенствуйте программу 21.8, чтобы работам можно было присваивать не только целочисленные номера, но и символические имена (см. программу 17.10).

21.93. Разработайте интерфейс АТД, который дает возможность клиентам ставить и решать задачи разностных ограничений.

21.94. Напишите класс, который реализует интерфейс из упражнения 21.93 на основе сведения задачи разностных ограничений к задаче поиска кратчайших путей в ациклических сетях.

21.95. Разработайте реализацию класса, который решает задачу поиска кратчайших путей из одного истока в ациклических сетях с отрицательными весами с помощью сведения к задаче разностных ограничений и интерфейса из упражнения 21.93.

21.96. Решение задачи поиска кратчайших путей в ациклических сетях из упражнения 21.95 предполагает существование реализации, которая решает задачу разностных ограничений. Что произойдет, если использовать реализацию из упражнения 21.94, которая предполагает существование реализации для задачи поиска кратчайших путей в ациклических сетях?

21.97. Докажите эквивалентность любых двух NP-трудных задач (т.е. выберите две таких задачи и докажите, что они сводятся друг к другу).

21.98. Сформулируйте явное построение, которое сводит задачу поиска кратчайших путей в сетях с целочисленными весами к задаче поиска гамильтонова пути.

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

21.100. Программа 21.8 не проверяет, разрешима ли задача календарного планирования, которую она выбирает в качестве входной (существует ли цикл). Охарактеризуйте графики, которые программа будет выводить для неразрешимых задач.

21.101. Разработайте интерфейс АТД, который позволяет клиентам ставить и решать задачи календарного планирования. Напишите класс, который реализует полученный интерфейс на основе сведения задачи календарного планирования работ к задаче поиска кратчайших путей в ациклических сетях (как в программе 21.8).

21.102. Добавьте в класс из упражнения 21.101 функцию (вместе с реализацией), которая выводит наиболее длинный путь в графике. (Такой путь обычно называется критическим путем.)

21.103. Напишите клиент для интерфейса из упражнения 21.101, который генерирует PostScript-программу для прорисовки календарного графика в стиле 3).

21.104. Разработайте модель для генерации задач календарного планирования. Воспользуйтесь полученной моделью для тестирования реализаций из упражнений 21.101 и 21.103 на приемлемом множестве задач разных размеров.

21.105. Напишите класс, который реализует интерфейс из упражнения 21.101, решая задачу календарного планирования работ с помощью ее сведения к задаче разностных ограничений.

21.106. Диаграмма PERT (Project Evaluation and Review Technique - сетевое планирование и управление) - это сеть, которая представляет задачу календарного планирования с ребрами в качестве работ (см. рис 21.25). Напишите класс, реализующий интерфейс календарного планирования из упражнения 21.101 на основе диаграмм PERT.

21.107. Сколько вершин содержит диаграмма PERT для задачи планирования с V работами и E ограничениями?

21.108. Напишите программы для взаимного преобразования задач календарного планирования работ, представленных ребрами (диаграммы PERT, см. упражнение 21.106), и представленных вершинами (см. рис 21.22).

(рис 21.25) Диаграмма PERT

Диаграмма PERT - это сетевое представление задачи календарного планирования, где работы представлены ребрами. Сеть в верхней части рисунка является представлением задачи календарного планирования с рис 21.22, где работы 0-9 представлены, соответственно, ребрами 0-1, 1-2, 2-3, 4-3, 5-3, 0-3, 5-4, 1-4, 4-2 и 1-5. Критическим путем в этом графике является наиболее длинный путь в данной сети.

Отрицательные веса

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

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

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

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

(рис 21.26) Пример сети с отрицательными ребрами

Это та же демонстрационная сеть, что и сеть с рис 21.1, только веса ребер 3-5 и 5-1 являются отрицательными. Естественно, данное изменение существенно влияет на структуру кратчайших путей, что легко увидеть, сравнивая матрицы расстояний и путей справа с соответствующими матрицами на рис 21.9. Например, кратчайший путь из 0 в 1 в этой сети - это путь 0-5-1, который имеет длину 0, а кратчайшим путем из 2 в 1 является путь 2-3-5-1 с длиной -0.17.

Например, в сети, приведенной на рис 21.26, кратчайший путь из 4 в 2 - это путь 4-3-5-1-2. Если увеличить веса всех ребер в графе на 0.38, чтобы сделать их все положительными, вес этого пути увеличится с 0.20 до 1.74. Однако вес 4-2 возрастет с 0.32 лишь до 0.70, так что кратчайшим путем из 4 в 2 станет это ребро. Чем больше ребер содержит путь, тем больше он " потяжелеет " от такого преобразования, поэтому результат с точки зрения предыдущего абзаца как раз противоположен тому, что требуется. Но даже если этот наивный подход не работает, идея преобразования сети в эквивалентную без отрицательных весов, но с теми же кратчайшими путями, вполне достойна внимания; в конце раздела мы рассмотрим алгоритм на основе этой идеи.

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

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

Доказательство леммы 21.18 оставляет возможность построения эффективных алгоритмов решения этой задачи, поскольку оно теряет смысл в отсутствие отрицательных циклов. Чтобы решить задачу поиска гамильтонова пути, необходимо иметь возможность решать задачи поиска кратчайших путей в сетях с огромным количеством отрицательных циклов.

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

Лемма 21.19. Задача календарного планирования с конечными сроками сводится к задаче поиска кратчайших путей в сетях, которые не содержат отрицательных циклов.

Доказательство. Рассуждения из доказательства леммы 21.15 показывают, что построение в доказательстве леммы 21.16 приводит к сетям, не содержащим отрицательных циклов. Из задачи календарного планирования мы создаем задачу разностных ограничений с переменными, которые соответствуют моментам начала работ, а из задачи разностных ограничений мы создаем сеть. Затем мы меняем знаки всех весов, чтобы перейти от задачи поиска наиболее длинных путей к задаче поиска кратчайших путей - преобразование, которое обращает знаки всех неравенств. Любой простой путь в сети из i в j соответствует последовательности неравенств, включающих переменные. Свертывая эти неравенства, получаем из существования такого пути, что $$$x_{i}-x_{j} \leq w_{ij}$$$, где w_ij - сумма весов на пути из i в j. Отрицательный цикл соответствует 0 в левой части этого неравенства и отрицательному значению в правой части, т.е. такой цикл не может существовать. $$$\blacksquare$$$

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

Обнаружение отрицательных циклов. Содержит ли данная сеть отрицательный цикл? Если да, то нужно найти один такой цикл.

С одной стороны, эта задача не обязательно простая (простые алгоритмы проверки циклов для орграфов неприменимы); с другой стороны, она не обязательно сложная (неприменимо и сведение из леммы 21.16 из задачи поиска гамильтонова пути). Поэтому вначале нужно разработать алгоритм решения этой задачи.

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

Арбитражные операции (валютные спекуляции). Многие газеты печатают таблицы курсов мировых валют (см., например, рис 21.27). Такие таблицы можно рассматривать как представления матрицами смежности для полных сетей. Ребро s-t с весом x означает, что можно конвертировать одну единицу валюты s в x единиц валюты t. Пути в сети задают многошаговые конверсии. Например, если существует также ребро t-w с весом у, то путь s-t-w представляет способ, позволяющий конвертировать одну единицу валюты s в xy единиц валюты w. Можно было бы ожидать, что xy равно весу ребра s-w во всех случаях, однако подобные таблицы являются сложной динамичной системой, где такая последовательность отнюдь не гарантирована. Если найдется вариант, где xy меньше, чем вес s-w, то мы сможем перехитрить систему. Предположим, что вес w-s равен z, и xyz > 1, тогда цикл s-t-w-s позволяет конвертировать одну единицу валюты s в более чем одну единицу (xyz) валюты s. То есть можно получить доход в 100(xyz - 1) процентов, конвертировав s в t, затем в w и снова в s. Данная ситуация является примером арбитражных операций (arbitrage), которые позволили бы нам получать безграничные доходы, если бы не существовало сил вне модели - как, например, ограничения на размер сделок. Чтобы преобразовать эту задачу в задачу поиска кратчайших путей, прологарифмируем все числа так, чтобы веса путей соответствовали сумме весов ребер вместо их умножения, а затем изменим их знаки, чтобы обратить неравенства. При этом веса ребер могут оказаться отрицательными или положительными, а кратчайший путь из s в t дает наилучший способ конвертации валюты s в валюту t. Цикл с наименьшим весом указывает лучшую возможность для арбитражных операций, хотя выгоден любой отрицательный цикл.

(рис 21.27) Арбитражные операции

Таблица в верхней части содержит переводные коэффициенты одной валюты в другую. Например, второй элемент в верхнем ряду означает, что за 1 доллар можно купить 1,631 единиц валюты P. Конвертация $1000 в валюту P и обратно должна дать $1000*1,631*0,613 = $999, т.е. потеря составляет $1. Однако конвертация $1000 в валюту P, затем в валюту Yи обратно в доллары дает $1000*1,631*0,411*1,495 = $1002 , т.е. прибыль 0,2%. Если составить новую таблицу (внизу) из отрицательных логарифмов всех чисел, то ее можно считать матрицей смежности для полной сети с весами ребер, которые могут быть как положительными, так и отрицательными. В этой сети узлы соответствуют валютам, ребра - конвертациям, а пути - последовательностям конвертаций. Описанная конверсия соответствует циклу $-P-Y-$ в графе с весом -0,489 + 0,890 - 0,402 = -0,002. Лучшая возможность для арбитражных операций соответствует наиболее короткому циклу в графе.

Можно ли обнаружить в сети отрицательные циклы или найти кратчайшие пути в сетях, которые не содержат отрицательных циклов? Существование эффективных алгоритмов для решения этих задач не противоречит NP-трудности общей задачи, которая была доказана в лемме 21.18, поскольку сведение задачи поиска гамильтонова пути к любой из этих задач не известно. А именно, сведение леммы 21.18 говорит о том, чего мы не можем сделать: создать алгоритм, который может гарантированно и эффективно найти путь с наименьшим весом в любой заданной сети, если в ней допускаются отрицательные веса ребер. Такая постановка задачи представляется слишком общей. Однако можно решить ограниченные версии этой задачи, хотя это и не так легко, как для других ограниченных версий данной задачи (положительные веса и ациклические сети), которые мы изучили выше в этой главе.

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

(рис 21.28) Отказ алгоритма Дейкстры (отрицательные веса)

В этом примере алгоритм Дейкстры решает, что кратчайшим путем из 4 в 2 является путь 4-2 (длиной 0.32), и упускает более короткий путь 4-3-5-1-2 (длиной 0.20).

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

) решает задачу обнаружения отрицательного цикла и задачу поиска кратчайших путей для всех пар вершин в сетях, которые содержат отрицательные циклы, за время, пропорциональное V³.

Доказательство. Доказательство леммы 21.8 не зависит от того, могут ли веса ребер быть отрицательными, однако при наличии ребер с отрицательными весами нужна другая интерпретация результатов. Каждый элемент в матрице свидетельствует о том, что алгоритм обнаружил путь этой длины. В частности, любой отрицательный элемент на диагонали матрицы расстояний означает наличие по крайней мере одного отрицательного цикла. При наличии отрицательных циклов мы не можем непосредственно делать какие-либо дальнейшие выводы, т.к. пути, которые алгоритм неявно проверяет, не обязательно просты: ведь некоторые из них могут содержать один и более витков по одному отрицательному циклу или нескольким. Однако если отрицательных циклов нет, то пути, которые вычисляются алгоритмом, просты, поскольку любой путь с циклом означает существование такого пути, который соединяет те же две точки, но содержит меньше ребер и имеет не больший вес (тот же путь с удаленным циклом). $$$\blacksquare$$$

Доказательство леммы 21.20 не дает конкретного рецепта, как найти конкретный отрицательный цикл, исходя из матриц расстояний и путей, вычисляемых по алгоритму Флойда. Мы оставляем это задание в качестве самостоятельного упражнения (см. упражнение 21.122).

Алгоритм Флойда решает задачу поиска кратчайших путей для всех пар вершин в графах, которые не содержат отрицательных циклов (см. рис 21.29). Учитывая отказ алгоритма Дейкстры в сетях, которые могут содержать отрицательные веса, алгоритм Флойда позволяет решить задачу для всех пар вершин в разреженных сетях без отрицательных циклов за время, пропорциональное V³. Если в таких сетях нужно решить задачу с одним истоком, можно применить это решение сложности V³ для всех пар вершин. Хотя при этом выполняется много лишней работы, это лучшее, что мы пока знаем для задачи с одним истоком. Можно ли разработать более быстрые алгоритмы для этих задач - такие, время выполнения которых сравнимо с алгоритмом Дейкстры для положительных весов ребер (E lg V для кратчайших путей из одного истока и VE lg V для кратчайших путей для всех пар вершин)? Мы можем ответить утвердительно на этот вопрос в отношении задачи для всех пар вершин; и можно снизить трудоемкость в худшем случае до VE для задачи с одним истоком.

(рис 21.29) Алгоритм Флойда (отрицательные веса)

Эта последовательность демонстрирует построение матриц всех кратчайших путей для орграфа с отрицательными весами с помощью алгоритма Флойда. Первый шаг совпадает с приведенным на рис 21.14. На втором шаге в игру вступает отрицательное ребро 5-1, и находятся пути 5-1-2 и 5-1-4. Алгоритм выполняет точно такую же последовательность шагов релаксации для любых весов, однако результаты отличаются.

А вот вопрос преодоления барьера VE для общей задачи поиска кратчайших путей из одного истока является по-прежнему открытым.

Следующий подход, разработанный Р. Беллманом (R. Bellman) и Л. Фордом (L. Ford) в конце 1950-х годов, предоставляет простую и эффективную основу для решения задач поиска кратчайших путей из одного истока в сетях без отрицательных циклов. Чтобы вычислить кратчайшие пути из вершины s, мы (как обычно) используем индексированный именами вершин вектор wt, такой, что wt[t] содержит длину кратчайшего пути из s в t. В wt[s] заносим 0, а во все другие элементы wt - большое сигнальное значение, после чего вычисляем кратчайшие пути следующим образом:

Просматриваем ребра сети в любом порядке и выполняем релаксацию вдоль каждого ребра. Выполняем V таких действий.

Общий метод выполнения V проходов по ребрам с просмотром ребер в любом порядке мы будем называть алгоритмом Беллмана-Форда (Bellman-Ford). Некоторые авторы применяют этот термин для описания еще более общего метода (см. упражнение 21.130).

Например, для графа, представленного списками смежности, алгоритм Беллмана-Форда поиска кратчайших путей из начальной вершины s можно реализовать так. Сначала занесем в элементы wt значения, большие, чем любая длина пути, а в элементы spt - пустые указатели, и затем выполним следующий код:

  wt[s] = 0;
  for (i = 0; i < G->V(); i++)
    for (v = 0; v < G->V(); v++)
      { if (v != s  spt[v] == 0) continue;
        typename Graph::adjIterator A(G, v);
        for (Edge* e = A.beg(); !A.end(); e = A.nxt())
          if (wt[e->w()] > wt[v] + e->wt())
            { wt[e->w()] = wt[v] + e->wt(); st[e->w()] = e; }
          }
      

Этот код демонстрирует простоту базового метода. Однако на практике он не используется: как вскоре будет показано, его простые модификации дают реализации, которые более эффективны для большинства графов.

Лемма 21.21. С помощью алгоритма Беллмана-Форда можно решить задачу поиска кратчайшего пути из одного истока в сетях без отрицательных циклов за время, пропорциональное VE.

Доказательство. Мы делаем V проходов по всем E ребрам, поэтому полное время будет пропорционально VE. Чтобы доказать, что это вычисление приведет к нужному результату, покажем методом индукции по i, что для всех вершин v после

i-го прохода значение wt[v] не больше, чем длина кратчайшего пути из s в v, который содержит i или менее ребер. Очевидно, это утверждение верно для i, равного 0. Полагая, что оно истинно для i, рассмотрим два возможных случая для каждой данной вершины v: среди путей из s в v с i + 1 или меньшим количеством ребер либо может, либо не может существовать кратчайший путь с i + 1 ребрами. Если самый короткий из путей с i+1 или менее ребрами из s в v имеет длину i или меньше, то wt[v] не изменится и останется допустимым. Иначе существует путь из s в v с i+1 ребрами, более короткий, чем любой путь из s в v с i или менее ребрами. Этот путь должен состоять из пути с i ребрами из s в некоторую вершину w с добавленным ребром w-v. По предположению индукции, wt[w] содержит верхнюю границу наиболее короткого расстояния из s в w, а (i+1)-й проход проверяет каждое ребро, является ли оно последним ребром в новом кратчайшем пути к конечной вершине ребра. В частности, проверяется ребро w-v.

После V- 1 итераций wt[w] содержит нижнюю границу длины любого кратчайшего пути из s в v с V- 1 или менее ребрами, для всех вершин v. Мы можем остановиться после V- 1 итераций, т.к. любой путь с V или более ребрами должен содержать цикл (с положительной или нулевой стоимостью), и, удалив этот цикл, можно отыскать путь с V- 1 или менее ребрами, который имеет такую же или меньшую длину. Поскольку wt[w] есть длина некоторого пути из s в v, это значение является также верхней границей длины кратчайшего пути, и таким образом, должно быть равно длине кратчайшего пути.

Хотя это и не было указано явно, то же самое доказательство показывает, что вектор spt содержит указатели на ребра в дереве кратчайших путей с корнем в s. $$$\blacksquare$$$

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

Программа 21.9 является прямой реализацией описанного алгоритма с использованием очереди FIFO, содержащей эти ребра, которые будут проверяться на каждом проходе. На рис 21.30 приведен пример работы этого алгоритма.

Программа 21.9. Алгоритм Беллмана-Форда

Эта реализация алгоритма Беллмана-Форда использует очередь FIFO всех вершин, для которых может оказаться эффективной релаксация по исходящему ребру. Мы выбираем вершину из очереди и выполняем релаксацию по всем ее ребрам. Если любое из них приводит к более короткому пути в некоторую вершину, мы заносим ее в очередь. Сигнальное значение G->V отделяет текущую серию вершин (которые изменились на последней итерации) от следующей серии (которые изменяются на данной итерации) и позволяет остановиться после G->V проходов.

  SPT(Graph G, int s) : G(G),
    spt(G.V()), wt(G.V(), G.V())
    { QUEUE<int> Q; int N = 0;
      wt[s] = 0.0;
      Q.put(s); Q.put(G.V());
      while (!Q.empty())
        { int v;
          while ((v = Q.get()) == G.V())
            { if (N++ > G.V()) return; Q.put(G.V()); }
          typename Graph::adjIterator A(G, v);
          for (Edge* e = A.beg(); !A.end(); e = A.nxt())
            { int w = e->w();
              double P = wt[v] + e->wt();
              if ( P < wt[w])
                { wt[w] = P; Q.put(w); spt[w] = e; }
            }
        }
    }
      

(рис 21.30) Алгоритм Беллмана-Форда (с отрицательными весами)

На этом рисунке показан результат поиска алгоритмом Беллмана-Форда кратчайших путей из вершины 4 в сети с рис 21.26. Алгоритм выполняет проходы, в которых проверяет все ребра, исходящие из всех вершин в очереди FIFO. Содержимое очереди показано под каждым чертежом графа, где затененные элементы представляют содержимое очереди, оставшееся с предыдущего прохода.

Когда мы находим ребро, которое может уменьшить длину пути из вершины 4 в конечную вершину этого ребра, мы выполняем операцию релаксации, которая помещает конечную вершину в очередь, а ребро - в SPT. Серые ребра на чертежах графа образуют SPT после каждого этапа, которое показано также в ориентированной форме в центре (все ребра ориентированы вниз). Мы начинаем с пустого SPT и вершины 4 в очереди (вверху). На втором проходе мы выполняем релаксацию вдоль ребер 4-2 и 4-3 и оставляем в очереди вершины 2 и 3.

На третьем проходе мы проверяем, но не выполняем релаксацию вдоль 2-3, а затем выполняем релаксацию вдоль 3-0 и 3-5, оставив в очереди вершины 0 и 5. На четвертом проходе мы выполняем релаксацию вдоль 5-1 и затем проверяем, но не выполняем релаксацию вдоль 1-0 и 1-5, оставив в очереди вершину 1. На последнем проходе (внизу) мы выполняем релаксацию вдоль 1-2. Алгоритм вначале действует как BFS, однако в отличие от всех других методов поиска на графах, он может изменять ребра дерева, как на последнем шаге.

Программа 21.9 эффективно решает задачи поиска кратчайших путей в реальных сетях с одним истоком, однако быстродействие в худшем случае все-таки остается пропорциональным VE. Для плотных графов время выполнения не лучше, чем для алгоритма Флойда, который находит все кратчайшие пути, а не только исходящие из одного истока. Для разреженных графов реализация алгоритма Беллмана-Форда в программе 21.9 может работать быстрее алгоритма Флойда вплоть до в V раз. Однако она работает почти в V раз медленнее, чем алгоритм Дейкстры в худшем случае на сетях без ребер с отрицательными весами (см. таблицу 19.2).

Были исследованы и другие вариации алгоритма Беллмана-Форда, и некоторые из них быстрее работают для задачи с одним истоком, чем версия с очередью FIFO в программе 21.9, но все они в худшем случае требуют времени, пропорционального по крайней мере VE (см., например, упражнение 21.132). Базовый алгоритм Беллмана-Форда был разработан десятки лет тому назад и, несмотря на впечатляющие достижения в повышении эффективности для множества других задач на графах, до сих пор не были открыты алгоритмы с лучшей эффективностью в худшем случае на сетях с отрицательными весами.

Кроме того, алгоритм Беллмана-Форда более эффективен, чем алгоритм Флойда, для обнаружения в сетях отрицательных циклов.

Лемма 21.22. С помощью алгоритма Беллмана-Форда можно решить задачу обнаружения отрицательного цикла за время, пропорциональное VE.

Доказательство. Основные положения доказательства леммы 21.21 справедливы даже при наличии отрицательных циклов. Если мы выполняем V-ю итерацию алгоритма, и один из шагов релаксации завершается успешно, то мы обнаружили кратчайший путь с V ребрами, который соединяет вершину s с некоторой вершиной в сети. Любой такой путь должен содержать цикл (соединяющий некоторую вершину w с собой), и в соответствии с предположением индукции этот цикл должен быть отрицательным: ведь чтобы w была включена в путь второй раз, путь из s во второе вхождение w должен быть короче пути из s в первое вхождение w. Этот цикл будет также присутствовать в дереве, поэтому обнаружить циклы можно и с помощью периодической проверки ребер из spt (см. упражнение 21.134).

Сказанное верно только для тех вершин, которые находятся в том же сильно связном компоненте, что и исток s. Чтобы обнаружить отрицательные циклы вообще, можно также вычислить сильно связные компоненты и обнулить веса для одной вершины в каждом компоненте (см. упражнение 21.126) или добавить фиктивную вершину с ребрами в каждую из остальных вершин (см. упражнение 21.127). $$$\blacksquare$$$

В заключение этого раздела рассмотрим задачу поиска кратчайших путей для всех пар вершин. Можно ли улучшить алгоритм Флойда, который выполняется за время, пропорциональное V³ ? Использование алгоритма Беллмана-Форда для решения задачи для всех пар вершин с помощью решения для каждой вершины задачи с одним истоком даст время выполнения в худшем случае, пропорциональное V2E . Мы не рассматриваем это решение более подробно, поскольку существует способ, гарантирующий решение задачи поиска всех путей за время, пропорциональное VE log К Он основан на идее, рассмотренной в начале этого раздела: преобразование исходной сети в сеть, которая содержит только неотрицательные веса и имеет такую же структуру кратчайших путей.

Фактически, у нас имеется большая свобода при преобразовании одной сети в другую с другими весами ребер, но с теми же кратчайшими путями. Предположим, что индексированный именами вершин вектор wt содержит произвольное присваивание весов вершинам сети G. Для этих весов определим операцию перевзвешивания (reweighting) графа следующим образом:

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

Чтобы перевзвесить сеть, необходимо перевзвесить все ребра сети.

Например, следующий простой код перевзвешивает сеть в соответствии с принятыми соглашениями:

  for (v = 0; v < G->V(); v++)
    { typename Graph::adjIterator A(G, v);
      for (Edge* e = A.beg(); !A.end(); e = A.nxt())
        e->wt() = e->wt() + wt[v] - wt[e->w()]
        }
      

Эта операция - простой линейный по времени процесс, который определен для всех сетей, независимо от весов. При этом кратчайшие пути в полученной сети остаются теми же, что и кратчайшие пути в исходной сети.

Лемма 21.23. Перевзвешивание сети не изменяет ее кратчайшие пути.

Доказательство. Для любых двух заданных вершин s и t перевзвешивание изменяет вес любого пути из s в t в точности на разность весов s и t. Это утверждение легко доказать методом индукции по длине пути. При перевзвешивании сети вес каждого пути из s в t изменяется на одно и то же значение, каким бы путь ни был - длинным или коротким. В частности, из этого факта непосредственно следует, что длина кратчайшего пути между любыми двумя вершинами в преобразованной сети совпадает с длиной кратчайшего пути между ними в исходной сети. $$$\blacksquare$$$

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

Перевзвешивание бесполезно в случае сетей с отрицательными циклами: эта операция не изменяет вес ни одного цикла, поэтому она не может удалить отрицательные циклы. Но для сетей без отрицательных циклов можно попытаться найти такое множество весов вершин, что перевзвешивание приведет к неотрицательным весам ребер, независимо от того, какими были первоначальные веса. С неотрицательными весами ребер мы можем затем решить задачу поиска кратчайших путей для всех пар вершин с помощью версии алгоритма Дейкстры для всех пар вершин. Например, на рис 21.31 приведен такой пример для нашей демонстрационной сети, а на рис 21.32 - вычисление кратчайших путей алгоритмом Дейкстры в преобразованной сети без отрицательных ребер. Следующая лемма показывает, что такое множество весов можно найти всегда.

Лемма 21.24. В произвольной сети без отрицательных циклов выберем любую вершину s и присвоим каждой вершине v вес, равный длине кратчайшего пути в v из s. Перевзвешивание сети с весами этих вершин дает в результате неотрицательные веса ребер для каждого ребра, которое соединяет вершины, достижимые из s.

Доказательство. Для любого заданного ребра v-w вес v равен длине кратчайшего пути в v, а вес w равен длине кратчайшего пути в w. Если v-w - конечное ребро на кратчайшем пути в w, то разность между весом w и весом v в точности равна весу v-w. Другими словами, перевзвешивание ребра даст нулевой вес. Если кратчайший путь через w не проходит через v, то вес v плюс вес v-w должен быть больше или равен весу w. То есть перевзвешивание ребра даст положительный вес. $$$\blacksquare$$$

(рис 21.31) Перевзвешивание сети

Для любого распределения весов на вершинах (вверху) можно выполнить перевзвешивание всех ребер в сети, добавив к весу каждого ребра разность весов его начальной и конечной вершин. Перевзвешивание не влияет на кратчайшие пути, поскольку оно одинаково изменяет веса всех путей, соединяющих каждую пару вершин. Вот, например, путь 0-5-4-2-3: его вес в первоначальной сети равен 0.29 + 0.21 + 0.32 + 0.50 = 1.32, а в перевзвешенной сети - 1.12 + 0.19 + 0.12 + 0.34 = 1.77; эти веса отличаются на 0.45 = 0.81 - 0.36, т.е. на разность весов вершин 0 и 3. Веса всех путей между 0 и 3 изменились на одну и ту же величину.

Как в случае применения алгоритма Беллмана-Форда для обнаружения отрицательных циклов, существуют два способа сделать вес каждого ребра неотрицательным в произвольной сети без отрицательных циклов. Либо можно начать с истока в каждом сильно связном компоненте, либо добавить фиктивную вершину с ребром нулевой длины в каждую вершину сети. В любом случае получится остовный лес кратчайших путей, которым можно воспользоваться для присвоения весов вершинам (вес пути из корня в данную вершину в ее SPT).

Например, значения весов, выбранные на рис 21.31, в точности равны длинам кратчайших путей из вершины 4, поэтому ребра в дереве кратчайших путей с корнем в 4 имеют нулевые веса в перевзвешенной сети.

Итак, мы можем решить задачу поиска кратчайших путей для всех пар вершин в сетях, которые содержат отрицательные веса ребер, но не имеют отрицательных циклов, следующим образом:

При помощи алгоритма Беллмана-Форда находим лес кратчайших путей в исходной сети.

Если алгоритм обнаружил отрицательный цикл, сообщаем об этом и завершаем работу.

Перевзвешиваем сеть на основе леса.

Применяем версию алгоритма Дейкстры для всех пар вершин к перевзвешенной сети.

После этих вычислений матрица путей содержит кратчайшие пути в обеих сетях, а матрица расстояний - длины путей в перевзвешенной сети. Эта последовательность шагов иногда называется алгоритмом Джонсона (Johnson) (см. раздел ссылок).

Лемма 21.25. С помощью алгоритма Джонсона можно решить задачу поиска кратчайших путей для всех пар вершин в сетях без отрицательных циклов за время, пропорциональное $$$VE\log_{d}{V}$$$, где d = 2, если E < 2V, и d = E/V в противном случае.

Доказательство. См. леммы 21.22-21.24 и резюме, подведенное в предыдущем абзаце. Граница времени выполнения в худшем случае непосредственно вытекает из лемм 21.7 и 21.22. $$$\blacksquare$$$

(рис 21.32) Все кратчайшие пути в перевзвешенной сети

Здесь приведены SPT-деревья для каждой вершины в обращении перевзвешенной сети с рис 21.31, которые можно получить с помощью алгоритма Дейкстры, вычислив кратчайшие пути в исходной сети с рис. 21.26 рис 21.26. Эти пути совпадают с путями сети до перевзвешивания.

Как на рис 21.9, векторы st на этих диаграммах представляют собой столбцы матрицы путей из рис 21.26. Векторы wt в этой схеме являются столбцами матрицы расстояний, но необходимо отменить пере-взвешивание для каждого элемента, вычтя вес начальной вершины и прибавив вес конечной вершины пути (см. рис 21.31). Например, из третьей строки снизу можно видеть, что в обеих сетях кратчайшим путем из 0 в 3 будет , можно вычислить его длину в исходной сети: вычтя вес 0 и прибавив вес 3, получим результат . Все кратчайшие пути, ведущие в вершину 4 в этой сети, имеют нулевцю длину, поскольку они использовались для перевзвешивания.

Для реализации алгоритма Джонсона мы объединяем реализацию из программы 21.9, код перевзвешивания, приведенный перед леммой 21.23, и реализацию алгоритма Дейкстры поиска кратчайших путей для всех пар вершин из программы 21.4 (или из программы 20.6 в случае плотных графов). Как было сказано в доказательстве леммы 21.22, для сетей, которые не являются сильно связными, придется соответствующим образом подправить алгоритм Беллмана-Форда (см. упражнения 21.135-21.137). Чтобы завершить реализацию интерфейса поиска кратчайших путей для всех пар вершин, можно либо вычислить истинные длины путей, вычитая вес начальной и прибавляя вес конечной вершины (т.е. отменить операцию перевзвешивания для путей) при копировании двух векторов в матрицы расстояний и путей в алгоритме Дейкстры, либо поместить эти вычисления в функцию GRAPHdist в реализации АТД.

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

Упражнения

21.109. Измените генераторы случайных сетей из упражнений 21.6 и 21.7, чтобы с помощью масштабирования выдавать веса из диапазона от а до b (где а и b принимают значения между -1 и 1).

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

21.111. Разработайте клиентские программы, которые используют генераторы из упражнений 21.109 и 21.110 для генерации сетей, содержащих большой процент отрицательных весов, но не более чем несколько отрицательных циклов, для как можно большего интервала значений V и E.

21.112. Найдите (в интернете или газетах) таблицу конвертации валют. Воспользуйтесь ей для построения таблицы арбитражных операций. Примечание: не берите таблицы, которые выводятся/рассчитываются из небольшого количества значений и которые поэтому не дают достаточно точной информации о курсах. Дополнительный совет: порвите всех на валютной бирже!

21.113. Постройте последовательность арбитражных таблиц, используя источник, найденный в упражнении 21.112 (каждый источник периодически публикует различные таблицы). Найдите в таблицах все возможности для совершения арбитражных операций и попытайтесь определить их характерные особенности. Например, сохраняются ли удобные возможности на протяжении нескольких дней, или же они быстро восстанавливаются сразу после возникновения?

21.114. Разработайте модель для генерации случайных задач арбитражных операций. Цель - генерировать таблицы, которые как можно более похожи на таблицы, используемые в упражнении 21.113.

21.115. Разработайте модель для генерации случайных задач календарного планирования с конечными сроками. Цель - генерировать нетривиальные, но обычно выполнимые задачи.

21.116. Измените интерфейс и реализации из упражнения 21.101, чтобы дать клиентам возможность ставить и решать задачи календарного планирования с конечными сроками, используя сведение к задаче поиска кратчайших путей.

21.117. Найдите ошибку в следующем рассуждении. Задача поиска кратчайших путей сводится к задаче разностных ограничений с помощью построения, используемого в доказательстве леммы 21.15, а задача разностных ограничений тривиально сводится к линейному программированию - поэтому, согласно лемме 21.17, линейное программирование является NP-трудным.

21.118. Сводится ли задача поиска кратчайших путей в сетях без отрицательных циклов к задаче календарного планирования с конечными сроками? (Эквивалентны ли эти две задачи?) Обоснуйте свой ответ.

21.119. Найдите цикл с наименьшим весом (лучшую возможность для совершения арбитражной операции) в примере, показанном на рис 21.27.

21.120. Докажите, что задача поиска цикла наименьшего веса в сети, которая может содержать ребра с отрицательными весами, является NP-трудной.

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

21.122. Разработайте класс, основанный на алгоритме Флойда, который предоставляет клиентам возможность проверить наличие в сети отрицательных циклов.

21.123. Воспользовавшись алгоритмом Флойда, покажите в стиле рис 21.29 вычисление всех кратчайших путей для сети, определенной в упражнении 21.1, но с отрицательными весами ребер 5-1 и 4-2.

21.124. Является ли алгоритм Флойда оптимальным для полных сетей (с V² ребрами)? Обоснуйте свой ответ.

21.125. Покажите в стиле рис 21.32 вычисление с помощью алгоритма Белл-мана-Форда всех кратчайших путей сети, определенной в упражнении 21.1, но с отрицательными весами ребер 5-1 и 4-2.

21.126. Разработайте класс, основанный на алгоритме Беллмана-Форда, который позволяет клиентам проверить наличие в сети отрицательных циклов, используя метод отдельного истока в каждом сильно связном компоненте.

21.127. Разработайте класс, основанный на алгоритме Беллмана-Форда, который позволяет клиентам проверить наличие в сети отрицательных циклов, используя фиктивную вершину с ребрами во все вершины сети.

о 21.128. Приведите семейство графов, для которых программа 21.9 затрачивает на поиск отрицательных циклов время, пропорциональное VE.

21.129. Покажите расписание, которое вычисляется программой 21.9 для задачи календарного планирования с конечными сроками из упражнения 21.89.

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

21.131. Измените реализацию алгоритма Беллмана-Форда в программе 21.9, используя в ней рандомизированную очередь вместо очереди FIFO. (Корректность этого метода доказана в упражнении 21.130.)

21.132. Измените реализацию алгоритма Беллмана-Форда в программе 21.9, чтобы вместо очереди FIFO использовать дек, в который ребра помещаются в соответствии со следующим правилом: если ребро уже находилось в деке, поместить его в начало (как в стеке), а если оно встречается в первый раз, то поместить его в конец (как в очереди).

21.133. Эмпирически сравните производительность реализаций из упражнений 21.131 и 21.132 с программой 21.9 на различных общих сетях (см. упражнения 21.109-21.111).

21.134. Измените реализацию алгоритма Беллмана-Форда в программе 21.9, чтобы реализовать функцию, которая возвращает индекс произвольной вершины из любого отрицательного цикла или -1, если сеть не содержит отрицательных циклов. При наличии отрицательного цикла эта функция должна также построить такой вектор spt, что переходы по ссылкам в этом векторе (начиная с возвращаемого значения) выполняют обход цикла.

21.135. Измените реализацию алгоритма Беллмана-Форда в программе 21.9, чтобы установить веса вершин так, как нужно для алгоритма Джонсона, воспользовавшись следующим методом. Каждый раз, когда очередь становится пустой, в векторе spt ищется вершина, вес которой еще не установлен, и алгоритм запускается повторно с этой вершиной в качестве истока (для установки весов всех вершин, находящихся в том же сильно связном компоненте, что и новый исток). Такая процедура повторяется, пока не будут обработаны все сильно связные компоненты.

21.136. Разработайте реализацию интерфейса АТД поиска кратчайших путей для всех пар вершин в разреженных сетях (основанную на алгоритме Джонсона), внеся соответствующие изменения в программы 21.9 и 21.4.

21.137. Разработайте реализацию интерфейса АТД поиска кратчайших путей для всех пар вершин в насыщенных сетях (основанную на алгоритме Джонсона) (см. упражнения 21.136 и 21.43). Эмпирически сравните полученную реализацию с алгоритмом Флойда (программа 21.5) для различных сетей общего вида (см. упражнения 21.109-21.111).

21.138. Добавьте в решение упражнения 21.137 функцию-член, которая позволяет клиенту уменьшить стоимость ребра. Она должна возвращать флаг, который указывает, создает ли это действие отрицательный цикл. Если нет, то необходимо обновить матрицы путей и расстояний, чтобы они содержали новые кратчайшие пути. Функция должна выполняться за время, пропорциональное V 2.

21.139. Добавьте в решение упражнения 21.138 функции-члены, которые позволяют клиентам вставлять и удалять ребра.

21.140. Разработайте алгоритм, который преодолевает барьер VE для задачи поиска кратчайших путей в общих сетях с одним истоком для частного случая, когда известно, что абсолютные значения весов ограничены некоторой константой.

Перспективы

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

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

Трудоемкости алгоритмов поиска кратчайших путей

Ограничение на веса	Алгоритм	Трудоемкость	Примечание
С одним истоком
Неотрицательные	Дейкстры	V2	Оптимальный (насыщенные сети)
Неотрицательные	Дейкстры (PFS)	E lgV	Осторожная граница
Без циклов	Очередь истоков	E	Оптимальный
Без отрицательных циклов	Беллмана-Форда	VE	Можно усовершенствовать?
Нет	Вопрос открыт	?	NP-трудный
Для всех пар вершин
Неотрицательные	Флойда	V3	Одинаково для всех сетей
Неотрицательные	Дейкстры (PFS)	VE lgV	Осторожная граница
Без циклов	DFS	VE	Одинаково для всех сетей
Без отрицательных циклов	Флойда	V3	Одинаково для всех сетей
Без отрицательных циклов	Джонсона	VE lgV	Осторожная граница
Нет	Вопрос открыт	?	NP-трудный

Общая задача поиска кратчайших путей в сетях, в которых веса ребер могут принимать отрицательные значения, является трудноразрешимой. Задачи поиска кратчайших путей представляют собой хорошую иллюстрацию той границы, которая часто отделяет трудноразрешимые задачи от легких, поскольку имеются многочисленные алгоритмы для решения различных вариантов этой задачи с различными ограничениями на сети: ребра только с положительными весами, или ацикличность, или даже подзадачи, где возможны отрицательные веса ребер, но нет отрицательных циклов. Некоторые алгоритмы оптимальны или почти оптимальны, хотя имеются существенные разрывы между наилучшей известной нижней границей, лучшим известным алгоритмом для задачи с одним истоком в сетях, которые не содержат отрицательных циклов, и для задачи всех пар вершин в сетях с неотрицательными весами.

Все эти алгоритмы основаны на небольшом количестве абстрактных действий и могут быть приведены в общей постановке. Конкретнее, единственные операции, которые выполняются над весами ребер - это сложение и сравнение: любая постановка, в которой эти операции имеют смысл, может служить платформой для алгоритмов поиска кратчайших путей. Как уже было сказано, эта точка зрения объединяет алгоритмы для вычисления транзитивного замыкания орграфа с алгоритмами поиска кратчайших путей в сетях. Сложность, привносимая отрицательными весами ребер, соответствует свойству монотонности для этих абстрактных операций: если можно гарантировать, что сумма двух весов никогда не меньше любого из весов, то можно использовать алгоритмы из разделов 21.2-21.4. Если же подобную гарантию дать нельзя, необходимо использовать алгоритмы из раздела 21.7. Инкапсуляция этих соображений в АТД не составляет особого труда и расширяет применимость данных алгоритмов.

Задачи поиска кратчайших путей выводят нас на перепутье между элементарными алгоритмами обработки графов и задачами, которые мы не можем решить. Это первые в ряду других классов аналогичных задач, в числе которых находятся задачи о сетевых потоках и линейное программирование. Как и при поиске кратчайших путей, в этих областях имеется четкая грань между легкими и трудноразрешимыми задачами. Имеются не только многочисленные эффективные алгоритмы, пригодные при соответствующих ограничениях, но и многочисленные возможности для поиска лучших алгоритмов - а также случаи, когда встречаются однозначно NP-трудные задачи.

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