Оптимизированная реализация алгоритма Дейкстры для разреженных графов (есть n вершин, m рёбер, но m существенно меньше n^2). ————————————————————————————————————————— Базовая версия алгоритма использует 3 массива D, P, U и состоит из n итераций, причём на очередной итерации выполняются две основные операции: - 1) выбирается вершина v с наименьшей величиной D[v] среди ещё не помеченных (операция требует O(n) времени) - 2) из вершины v производятся релаксации: просматриваются все рёбра (v,to), исходящие из вершины v, и для каждой такой вершины to алгоритм пытается улучшить значение D[to] (требует O(1) времени) Операция (1) выполняется всего O(n) раз, а операция (2) - O(m) раз, поэтому базовая реализация Дейкстры забирает O(n^2+m) времени. —————————————————————————————————————————— Для разреженных графов есть смысл улучшать время выполнения операций первого типа, не сильно ухудшая при этом время выполнения операций второго типа. Можно использовать вспомогательные структуры данных (кучи или очереди приоритетов), позволяющие делать операции обоих типов за О(log n). Тогда можно ожидать, что сложность алгоритма станет O(n*log n + m*log n). Булевский массив U алгоритма, для каждой вершины v хранящий, помечена она ещё или нет, - становится не нужен. Его роль выполняет heap или priority_queue.
public class DijkstraFast
Тип | Имя | Описание |
---|---|---|
DijkstraFast(Int32, InternodeTraversalCost, NearbyNodesHint) |
Тип | Имя | Описание |
---|---|---|
Equals(Object) | Определяет, равен ли заданный объект текущему объекту. (Наследуется от Object.) | |
GetHashCode() | Служит хэш-функцией по умолчанию. (Наследуется от Object.) | |
GetMinimumPath(Int32, Int32, Single) | ||
GetType() | Возвращает объект Type для текущего экземпляра. (Наследуется от Object.) | |
Perform(Int32) | ||
Perform2(Int32) | ||
ToString() | Возвращает строку, представляющую текущий объект. (Наследуется от Object.) |