Глава 21, Кратчайшие пути. всегда выбирая такое из следующих ребер, которое дает кратчайший путь из источника в вершину, не включенную в SPT

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

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

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

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

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

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

Рисунок 21.10 иллюстрирует эволюцию SPT для типового графа при вычислении по алгоритму Дейкстры, а на рис. 21.11 показан рисунок большего ориентированного дерева SPT. Хотя алгоритм Дейкстры отличается от алгоритма Прима для MST только способом выбора приоритетов, деревья SPT обладают характерными особенностями, отличающи­ми их от MST. У них корень расположен в начальной вершине, и все ребра направлены в сторону от корня, тогда как MST не имеют корня и являются неориентированными. Мы иногда представляем MST как направленные деревья с корнем, например, когда мы ис­пользуем алгоритм Прима, но такие структуры еще имеют характерные отличия от SPT (сравните представление ориентированного дерева на рис. 20.9 с представлением на рис. 21.11). Действительно, природа SPT отчасти зависит от выбора начальной вершины, как это видно из рис. 21.12.

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

РИСУНОК 21.10. АЛГОРИТМ ДЕЙКСТРЫ

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

На первом шаге мы добавляем 0 к дереву, а ребра, выходящие из него, 0-1 и 0-5, — к бахроме (рисунок вверху). На втором шаге мы перемещаем самое короткое из этих ребер, 0-5, из бахромы в дерево и проверяем ребра, отходя­щие от него: ребро 5-4 добавляется к бахроме, а ребро 5-1 удаляется, поскольку оно не является частью пути из 0 в 1, более коротко­го, чем известный путь 0-1 (второй рисунок сверху). Приоритет ребра 5-4 в бахроме определяется длиной пути из 0, который оно представляет, 0-5-4. На третьем шаге мы перемещаем 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. Кратчайшие пути

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

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

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

р = e-> wt() (вес ребра) на

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

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

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

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

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

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

РИСУНОК 21.12. ПРИМЕРЫ SPT

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

Как и в главе 20, ребра, которые соединяют вершины дерева с вершинами, не вклю­ченными в дерево, содержатся в обобщенной очереди, называемой бахромой (fringe). Для реализации этой обобщенной очереди используются приоритеты, а также предусматри­вается настройка приоритетов таким образом, чтобы объединить алгоритмы DFS, BFS и Прима в одной реализации (см. раздел 20.3). Эта схема поиска по приоритетам (PFS, Priority-First Search) содержит в себе также алгоритм Дейкстры. То есть, изменение опе­ратора присваивания Р в программе 20.7 на

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

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

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

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