Оптимизированная реализация алгоритма Дейкстры для разреженных графов (есть 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.

• Пространство имен: Topomatic.Glg.FastDijkstra
• Сборка: Topomatic.Glg (в Topomatic.Glg.dll)

• System.Object
  • Topomatic.Glg.FastDijkstra.DijkstraFast

public class DijkstraFast