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