Алгоритм Дейкстры в PascalABC.NET: кратчайшие пути с PriorityQueue

В предыдущей статье о PriorityQueue мы познакомились с очередью с приоритетами. Одно из её классических применений — алгоритм Дейкстры, который находит кратчайшие пути от одной вершины графа до всех остальных.

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

В этой статье используется компилятор PascalABC.NET для .NET 10: класс PriorityQueue доступен в современной библиотеке .NET, но отсутствует в .NET Framework 4.7.2.

Идея алгоритма

Пусть требуется найти кратчайшие расстояния от начальной вершины start. Для каждой вершины v будем хранить dist[v] — минимальное найденное к текущему моменту расстояние от start до v. Пока вершина не обработана, это расстояние ещё может улучшиться.

В начале известно только расстояние от стартовой вершины до самой себя:

\operatorname{dist}[\mathrm{start}] = 0, \qquad \operatorname{dist}[v] = +\infty \quad (v \ne \mathrm{start}).

На каждом шаге алгоритм выбирает ещё не обработанную вершину с минимальным известным расстоянием и рассматривает все выходящие из неё рёбра. Пусть из вершины u ведёт ребро веса w в вершину v. Если

\operatorname{dist}[u] + w < \operatorname{dist}[v],

то путь до v через u короче уже найденного. Обновим расстояние и добавим вершину в очередь с новым приоритетом:

if dist[u] + w < dist[v] then
begin
  dist[v] := dist[u] + w;
  q.Enqueue(v,dist[v])
end

Такое улучшение расстояния называется релаксацией ребра. Для быстрого выбора вершины с минимальным текущим расстоянием используется PriorityQueue: номер вершины помещается в очередь как элемент, а расстояние до неё — как приоритет.

Реализация

Рассмотрим неориентированный граф из шести вершин с номерами от 0 до 5. Программа запускает алгоритм Дейкстры из вершины 0 и вычисляет кратчайшее расстояние до каждой вершины графа. Сам маршрут она не восстанавливает — только его минимальную длину.

uses System.Collections.Generic;

begin
  var n := 6;

  var edges := [
    (0,1,7), (0,2,9), (0,5,14),
    (1,2,10), (1,3,15),
    (2,3,12), (2,5,2),
    (3,4,6), (4,5,9)
  ];

  var graph := ArrGen(n,i -> new List<(integer,integer)>);

  foreach var (u,v,w) in edges do
  begin
    graph[u].Add((v,w));
    graph[v].Add((u,w))
  end;

  var start := 0;

  var dist := ArrFill(n,integer.MaxValue);
  var used := new boolean[n];
  dist[start] := 0;

  var q := new PriorityQueue<integer,integer>;
  q.Enqueue(start,0);

  while q.Count > 0 do
  begin
    var u := q.Dequeue;

    if used[u] then
      continue;

    used[u] := True;

    foreach var (v,w) in graph[u] do
      if dist[u] + w < dist[v] then
      begin
        dist[v] := dist[u] + w;
        q.Enqueue(v,dist[v])
      end
  end;

  dist.Println
end.

Граф хранится в виде списков смежности: для каждой вершины хранится список пар «соседняя вершина, вес ребра». Выражение ArrGen создаёт отдельный список для каждой вершины.

Например, тройка (2,5,2) в массиве edges означает, что вершины 2 и 5 соединены ребром веса 2. Поскольку граф неориентированный, каждое ребро добавляется в списки обеих вершин. Для ориентированного графа следует оставить только graph[u].Add((v,w)) — добавление ребра в заданном направлении.

Что вычисляет программа

Результат работы программы:

0 7 9 21 20 11

Элементы массива соответствуют вершинам с номерами от 0 до 5:

Вершина	0	1	2	3	4	5
Расстояние	0	7	9	21	20	11

Например, кратчайшее расстояние от 0 до 1 равно $7$ , до 2 — $9$ , а до 5 — $11$ . Хотя существует непосредственное ребро $0 \to 5$ веса $14$ , путь $0 \to 2 \to 5$ короче:

9 + 2 = 11 < 14.

До вершины 4 кратчайшее расстояние равно $20$ : путь $0 \to 2 \to 5 \to 4$ имеет длину

9 + 2 + 9 = 20.

Таким образом, программа не просто находит ближайшую вершину и не ищет один заранее заданный маршрут. Она за один запуск вычисляет кратчайшие расстояния от выбранной стартовой вершины до всех остальных вершин графа.

Зачем нужна PriorityQueue

Без очереди с приоритетами на каждом шаге можно было бы перебирать все ещё не обработанные вершины и искать среди них вершину с минимальным dist. Такой выбор требует линейного просмотра массива. Для разреженных графов PriorityQueue позволяет организовать поиск эффективнее: Dequeue извлекает запись с наименьшим приоритетом, то есть с наименьшим расстоянием.

Есть важная особенность реализации: если для вершины сначала найден путь длины $20$ , а затем более короткий путь длины $15$ , вершина помещается в очередь ещё раз — уже с новым приоритетом. Старая запись остаётся в очереди.

Это происходит и в нашем примере: вершина 5 сначала добавляется с расстоянием $14$ , а после обработки вершины 2 — ещё раз с расстоянием $11$ . Запись с приоритетом $11$ будет извлечена раньше записи с приоритетом $14$ .

Поэтому одна вершина может оказаться в очереди несколько раз. Массив used позволяет обработать её только один раз, пропуская все последующие записи:

if used[u] then
  continue;

Когда вершина впервые извлекается из очереди, её кратчайшее расстояние уже окончательно найдено. Почему? Выбрана необработанная вершина с минимальным известным расстоянием, а продолжение пути через другие необработанные вершины не может сделать его короче: все веса неотрицательны. После этого вершина отмечается как обработанная, а её рёбра просматриваются ровно один раз.

Ограничения и эффективность

Алгоритм Дейкстры работает только для графов с неотрицательными весами рёбер. Нулевые веса допустимы, отрицательные — нет. Это принципиальное условие корректности алгоритма.

В программе integer.MaxValue используется как условная бесконечность. Если вершина недостижима из start, её расстояние останется равным этому значению. В очередь попадают только вершины с найденным конечным расстоянием, поэтому условная бесконечность не участвует в сложении.

Для небольших весов в нашем примере типа integer достаточно. При больших весах или длинных путях сумма dist[u] + w может переполниться. В таких задачах нужно выбирать более широкий тип, например int64, и для расстояний, и для приоритетов очереди, а также проверять, что суммы помещаются в выбранный тип. Все реальные конечные расстояния должны быть меньше значения, выбранного в качестве бесконечности.

Обозначим число вершин через $V$ , а число рёбер — через $E$ . Для приведённой реализации с повторным добавлением вершин очередь может содержать $O(E)$ записей. С учётом инициализации массивов оценка времени работы составляет

O\bigl(V + E\log(E + 2)\bigr).

Для простого графа, без параллельных рёбер, её обычно записывают в привычной форме

O\bigl((V + E)\log V\bigr).

Память для списков смежности, массивов и очереди составляет $O(V + E)$ . Поэтому такая реализация особенно полезна для больших разреженных графов.

Если нужно освежить основные операции очереди, вернитесь к статье «PriorityQueue в PascalABC.NET: очередь с приоритетами в .NET 10».