Главная » Java, Структуры данных и алгоритмы » Алгоритм Дейкстры

0

Основная идея применения каскадного метода в задачах определения кратчайших маршрутов заключается в выполнении «взвешенного» поиска в ширину в узле v. В частности, используем каскадный метод в алгоритме, который итеративно создает вокруг узла v «окружение» из узлов, входящих • в это множество в порядке их расстояний от v, выбирая при каждой итерации узел, наиболее близкий к v. Алгоритм заканчивает работу, как только узлы заканчиваются, то есть определены кратчайшие пути из v до всех других узлов в G. Несмотря на простоту, этот подход очень эффективен.

Каскадный метод определения кратчайшего маршрута

Применение каскадного метода в задачах определения кратчайших маршрутов привело к появлению алгоритма, известного как алгоритм Дейкстры (Dijkstra’s algorithm). Хотя использование этого метода для решения других проблем графов не всегда эффективно, тем не менее существует область (так называемая «задача коммивояжера»), в которой его применение дает наилучшее решение проблемы. В данном случае речь идет о вычислении кратчайшего маршрута и создании остовного дерева минимального размера.

Для упрощения описания алгоритма Дейкстры предположим, что исходный граф G ненаправленный (то есть все его пути не направлены) и простой (то есть не содержит петель или параллельных путей). Обозначим пути в G как ненаправленные пары узлов (u,z).

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

Восстановление путей

Для каждого узла и в Копределим метку D[u], которую будем использовать при вычислении расстояния в G от v до и. Назначение этих меток состоит в том, чтобы сохранять длину наилучшего маршрута, обнаруженного на текущий момент. Изначально D[v] = 0, a D[u] = +00 для любого и ф v. Определим также множество С «окружения» узлов, которое будет изначально пустым множеством 0. При каждой итерации выбирается узел w, не входящий в множество С, с наименьшей меткой D[u] и вводится в С.

В первой итерации в С, естественно, вводится сам v. Как только новый узел оказывается в С, обновляем D[z] каждого узла z, смежного с и, но расположенного за пределами С, так, чтобы он отражал возможность стать следующим и более удачным вариантом. Эта операция обновления получила название процедуры восстановления (relaxation), так как предыдущее значение может быть пересмотрено с целью его улучшения и приближения к истинному значению (сравним это с пружиной, которая была растянута, а затем вернулась в исходное состояние). При применении алгоритма Дейкстры восстановление выполняется для пути (u,z) так, чтобы, вычислив новое значение D[u], можно было проверить, имеется ли лучшее значение D[z]. Операция восстановления выглядит так:

Восстановление пути

if D[u] + w((u,z)) < D[z] then

D[z] <- D[u] + w((u,z))

Во фрагменте кода 12.12 приводится псевдокод алгоритма Дейкстры. Заметьте, что для хранения узлов, не входящих в С, используется приоритетная очередь.

Алгоритм ShortestPath(G,v):

Input: простой ненаправленный взвешенный граф G, пути которого имеют неотрицательный вес, и определенный узел v в G.

Output: метка D[u] для каждого узла и в G, обозначающая длину наикратчайшего маршрута от v до и.

Инициировать D[v] <- 0 и D[u] <- +00 для каждого узла и ф v.

Пусть очередь р приоритетами Q содержит все узлы G, используя

имена D в качестве ключей.

while Q не является пустой do {ввести новый узел и в облако} и <- Q.removeMin()

for каждого узла z, смежного с и, чтобы z при этом был в О, do {выполнить восстановление в пути (u,z)} if D[u]+w((u,z)) < D[z] then D[z] <- D[u]-fw((iy,z)) заменить ключ узла zb Она D[z]. return ключ D[u] каждого узла и

Фрагмент кода 12.12. для решения задачи кратчайшего маршрута

Несколько итераций алгоритма проиллюстрированы на рис. 12.15 и 12.16.

 

 

Рис. 12.15. Выполнение алгоритма Дейкстры во ‘взвешенном графе. Стартовым узлом служит BWI. В прямоугольнике рядом с каждым узлом v приведена метка Z)[v]. Символ • используется вместо +оо. Пути дерева кратчайших маршрутов выделены жирными стрелками, а для каждого узла и за пределами облака текущий лучший путь для ввода и в «окружение» отмечен пунктирной линией

Рис. 12.16. Пример алгоритма Дейкстры (продолжение)

Почему это работает

Наиболее интересным и, наверное, удивительным является то, что в момент ввода узла ив С его метка D[u] хранит правильное значение длины кратчайшего маршрута от v до и. Таким образом* по завершении работы алгоритм высчитывает кратчайшее расстояние от v до каждого из узлов в С, то есть решает поставленную задачу.

Как же происходит, что расстояние от v до и оказывается равным значению метки D[u] в тот момент, когда узел и вводится в С (что одновременно является и моментом удаления и из приоритетной очереди (?)? Ответ на этот вопрос связан с отсутствием в графе путей с отрицательным весом, что определяет верное исполнение каскадного метода.

Утверждение 12.15. В алгоритме Дейкстры всякий раз, когда узел и вводится в облако, метка D[u] равна d(v,u), то есть длине кратчайшего маршрута от v до и.

Доказательство. Предположим, что D[t] > d(v,t) для некоторого узла t в F, а и пусть будет первым введенным в облако С узлом (то есть удаленным из Q), в результате D[u] > d(v,u). Существует кратчайший маршрут Р от v до и (так как в противном случае d(v,u) = +00 = D[u]\). Рассмотрим момент, в который и вводится в С, когда z будет первым узлом в Р (при переходе от v к и), не входящим в С в этот момент. Пусть у будет предшественником z в маршруте Р (заметим, что может быть у = v) (см. рис. 12.17). Известно, что выбор z означает наличие у к этому моменту в С. Более того, проверено (и, возможно, обновлено) D[z], так что в этот момент выполняется

Рис. 12.17. Схематическая иллюстрация доказательства утверждения 12.15

Рассмотрим реализацию графа с помощью структуры списка смежности. Эта структура позволяет проходить смежные с v узлы в процессе стадии восстановления за время, пропорциональное их количеству. Однако по-прежнему необходимо привести подробности реализации основной структуры данных алгоритма — приоритетной очереди Q.

Наиболее эффективной реализацией приоритетной очереди является пирамида (см. раздел 7.3). Это позволяет выбрать узел и с наименьшей /)-меткой (вызов метода removeMin) за время <9(log п). Как указано в псевдокоде, при каждом обновлении метки D[z\ необходимо обновлять ключ z в приоритетной очереди. Если Q реализована пирамидой, то обновление ключа может выполняться его удалением, а затем — повторным вводом z уже с новым ключом. Если Q поддерживает локаторную модель (см раздел 7.4), то обновление ключа легко реализуется за 0(log п) времени, поскольку локатор для узла z позволит Q получить прямой доступ к объекту, хранящему z в стопке (см. раздел 7.4). Такая реализация алгоритма Дейкстры выполняется за 0((п + m)log п) времени.

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

•      вводим друг за другом все узлы в Q с начальными значениями ключей за 0(log п) времени (или за О(п) времени с помошью восходящего построения стопки (см. п. 7.3.5));

•      при каждой итерации while-цикла требуется 0(log п) времени на удаление узла и из Q и 0(degree(v)log п) времени на выполнение процедуры восстановления в пути, проходящем через и\

•      общее время выполнения while-цикла составит

что, согласно утверждению 12.6, равно

Заметим, что при выражении этой функции через п в наихудшем случае врёмя составит 0(п2 log п)\

Другой способ реализации алгоритма Дейкстры

Рассмотрим еще один способ реализации приоритетной очереди с помощью несортированной последовательности. Естественно, это потребует С1(п) времени на извлечение наименьшего элемента, но позволит ускорить Обновление ключей при условии, что Q поддерживает локаторную модель (раздел 7.4). В частности, обновление ключей реализуется в процессе процедуры восстановления за 0(1) времени. Это происходит простым изменением значения ключа, как только в Q отыскивается объект для обновления. Следовательно, в результате данной реализации время выполнения составляет 0(п2 + т), что можно упростить до 0(п2), поскольку обрабатывается простой граф G.

Сравнение двух реализаций

На выбор имеются два варианта реализации приоритетной очереди по алгоритму Дейкстры: на основе локаторной модели для пирамиды, выполняющийся за 0((п + m)log п), и на основе локаторной модели для несортированной пирамиды, выполняющийся за 0(п2) времени. Поскольку оба варианта достаточно просты при кодировании, то с этой точки зрения они равны, как и с точки зрения времени выполнения в наихудших случаях. Но все же в наихудших случаях следует предпочесть реализацию, в основу которой положена пирамида, если количество путей в графе невелико (то есть т < n2/log п). Если же количество путей достаточно велико (т > п2/log п), лучше применять реализацию на основе последовательности,

t

Утверждение 12.16. Имея простой ненаправленный взвешенный граф G из п узлов и т путей, где вес каждого пути положителен, и узел v графа G, алгоритм Дейкстры вычисляет расстояние от v до остальных узлов в G за 0((п + m)log п) времени или, как альтернатива, за 0(п2) времени в наихудшем рлучае.

Выполнив упражнение М-12.16, можно модифицировать алгоритм Дейкстры для получения дерева Г, корнем которого является v, таким образом, чтобы маршрут от v до узла и был кратчайшим.

Программирование алгоритма Дейкстры на Java

Имея псевдокод алгоритма Дейкстры, рассмотрим Java-код этого алгоритма для ненаправленного графа с положительными целочисленными значениями веса. Для реализации алгоритма используем абстрактный класс Dijkstra (фрагменты кода 12.13-12.15), в которых объявляем абстрактный метод weight(e) определения веса пути е. Предполагается, что класс Dijkstra можно в дальнейшем расширять подклассами, реализующими метод weight(e) (класс MyDijkstra во фрагменте кода 12.16).

/** для решения задачи определения кратчайшего

*                     маршрута в ненаправленном графе, пути которого имеют

*                     положительный целочисленный вес.

*                      Классы, расширяющие абстрактный класс, должны определять метод

*                     weight(e),

* извлекающий вес каждого пути. 7 public abstract class Dijkstra { /** Выполнить алгоритм. 7

public void execute(lnspectableGraph g, Vertex source) { graph = g; dijkstraVisit(source);

/** Атрибут расстояния до узла. 7 protected Object DIST = new Object(); /** Установить расстояние до узла. 7 protected void setDist(Vertex v, int d) { v.set(DIST, new Integer(d));

}

/** Определить расстояние до узла от исходного узла. Метод возвращает

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

*                     вызван метод execute. 7 public int getDist(Vertex и) {

return ((Integer) u.get(DIST)).intValue();

}

/** Этот абстрактный метод Должен быть определен подклассом. 7

*                     ©return weight пути е. 7 protected abstract int weight(Edge e); /** Значение бесконечности. 7

public static final int INFINITE = lnteger.MAX_VALUE;

/** Исходный граф. 7

protected InspectableGraph graph;

/** Вспомогательная приоритетная очередь. 7

protected PriorityQueue Q;

Фрагмент кода 12.13. Класс Dijkstra реализации алгоритма Дейкстры (продолжение во фрагментах кода 12.14 и 12.15)

Основные вычисления в алгоритме выполняет метод dijkstraVisit. Здесь также используется приоритетная очередь, поддерживающая лока- торную модель. Узел и вводится в Q методом insert, возвращающим локатор мв С, который «присоединяется» к и методом setLoc и извлекается методом getLoc. Заметим, что установление соответствия локаторов узлам представляет собой разновидность декоратора (п. 12.3.1). Вместо использования дополнительной структуры данных для меток D[u] воспользуемся тем, что D[u] является ключом узла и в Q, то есть D[u] можно извлекать по локатору узла и в Q. Изменение метки узла z на d в процедуре восстановления соответствует вызову метода replaceKey(/,d), где / — локатор z в Q.

/** Непосредственное выполнение алгоритма Дейкртры.

* @param v исходный узел. */ protected void dijkstraVisit (Vertex v) {

// инициализирует приоритетную очередь Q и складирует в ней все // узлы

Q = new ArrayHeap(new lntegerComparator()); for (Vertexlterator vertices = graph.vertices(); vertices.hasNext()); { Vertex u = vertices.nextVertex(); int u_dist; if (u==v)

u_dist = 0; else

u_dist = INFINITE; Locator ujoc = Q.insert(new lnteger(u_dist), u); setLoc(u, ujoc);

}

// создает облако, вводя по одному узлу за раз while (!Q.isEmptyO) {

// удаляет из Q и вводит в облако узел с наименьшим расстоянием

Locator ujoc = Q.min();

Vertex u = getVertex( ujoc);

int u_dist = getDist(uJoc);

Q.remove(ujoc); // удаляет u из Q

setDist(u, u_dist); // расстояние до u конечное

destroyLoc(u); // удаляет локатор, ассоциируемый с u

if (u_dist = INFINITE)

continue; // недостижимые узлы не обрабатывать // проверить все соседние с и узлы и обновить их расстояния for (Edgelterator edges = graph.incidentEdges(u); edges.hasNext()); { Edge e = edges.nextEdge(); Vertex z = graph.opposite(u,e);-

if (hasLoc(z)) { // убедиться, что z в Q, а не в "окружении" (облако) int e_weight = weight(e); Locator zjoc t= getLoc(z); ^ , int z_dist = getDist(zJoc); if ( U-dist + e_weight < z_dist ) // восстановление пути

// e = (u,z)

Q.replaceKey(z_loc, new lnteger(u_dist + e_weight));

} ‘

}

}

}

Фрагмент кода 12.14. Метод dijkstra Visit класса Dijkstra

/** Атрибут локаторов узла в Q. */ protected Object LOC = new Object();

/** Убедиться в наличии локатора, ассоциируемого с узлом. */ protected boolean hasLoc(Vertex v) { return v.has(LOC);

}

/** Получить локатор узла из Q. */ protected Locator getl Loc(Vertex v) { – return (Locator) v.get(LOC); /** Ассоциировать с узлом его локатор в Q. */ protected void setLoc(Vertex v, Locator 1) { v.set(LOC, I);

}

/** Удалить локатор, ассоциируемый с узлом. */

protected void destroyLoc(Vertex v) { v.destroy(LOC); }

/** Получить узел, ассоциируемый с локатором. */ protected Vertex getVertex(Locator I) { return (Vertex) l.element();

}

/** Получить расстояние до узла, имея его локатор в Q. */ protected int getDist(Locator I) { return ((Integer) l.key()).intValue();

}

Фрагмент кода 12.15. Вспомогательные методы класса Dijkstra. Эти методы предполагают, что узлы в графе могут оформляться некоторыми элементами-характеристиками

/** Специализация класса Dijkstra для выделения веса пути из * элемента оформления. */, public class MyDijkstra extends Dijkstra { Л* Атрибут веса пути. */ protected Object WEIGHT; /** Конструктор для установки атрибута веса. */ public MyDijkstra(Object weight_attribute) { WEIGHT = weight.attribute;

}

/** Вес пути хранится в атрибуте WEIGHT. */ public int weight(Edge e) {

return ((Integer) e.get(WEIGHT)).intValue();

}

}

Фрагмент кода 12.16. Класс MyDijkstra, расширяющий Dijkstra и обеспечивающий конкретную реализацию метода weight(e)

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии