По заданным вершинам  i₀  и  i₊  требуется найти путь с началом  i₀  и  концом i₊, имеющий минимальный суммарный вес.

Обычно эта задача называется задачей о кратчайшем пути.

Мы рассмотрим несколько способов решения этой задачи. Но в них во всех есть характерная особенность: задача рассматривается как одна из целого семейства подобных задач, и все они решаются вместе.

При таком подходе решение каждой из задач становится очень простым.

Легко видеть, что при условии положительности длин дуг искомый оптимальный путь будет простым. Мы рассмотрим и случай, когда предположение о положительности длин дуг не делается. Тогда оптимальный путь может и не быть простым, и приходится делать специальные предположения, чтобы исключить пути неограниченной звенности (напоминаю, что звенность пути — это число дуг в нем).

Этот способ, в основу которого положен алгоритм Уоршелла для построения транзитивного замыкания отношения, был разработан Робертом Флойдом (1936-2001) и называется алгоритмом Флойда-Уоршелла.

Рассмотрим матрицу  v[M,M], в которой на месте  v[i1,i2]  будет вычисляться длина кратчайшего пути от  i1  до  i2. Попутно будет вычисляться матрица решений, по которым устанавливается сам кратчайший путь,  d[M,M]. О смысле элементов этой матрицы мы будем говорить позднее.

Матрица  v[M,M]  первоначально заполняется «бесконечными» значениями — очень большим числом, которое заведомо больше веса любого пути. Матрица d[M,M] заполняется нулями. Затем мы учитываем имеющиеся дуги и их веса. Для этого выполняется такой цикл

  for j in N do
    i1 := iBeg(j); i2 := iEnd(j);
    if v[i1,i2] > w[j] then
      v[i1,i2] := w[j]; d[i1,i2] := j
    fi
  od

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

  for i in M do
    for j in M do
      for k in M do
        if v[j,i]+v[i,k] < v[j,k] then
          v[j,k] := v[j,i]+v[i,k]; d[j,k] := -i
        fi
      od
    od
  od

В матрице d[M,M] первоначально записаны номера используемых дуг, а затем, со знаком минус, записываются номера вершин (ага, этим мы предполагаем — о чем ранее не говорилось, — что индексы вершин и индексы дуг являются положительными числами). При построении кратчайшего пути от вершины  i1  до вершины  i2, если число j = d[i1,i2] положительно, то путь состоит из дуги j, если же отрицательно, то путь является конкатенацией путей от  i1  до  −j  и от  −j  до  i1.

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

В методе Беллмана мы рассматриваем не матрицу, а вектор v[M], который в предыдущих обозначениях соответствует строке  i₀  матрицы  v[M,M]. Оказывается, можно вести все требуемые вычисления, ограничиваясь всего одной строкой.

Первоначально запишем в v[M] «кратчайшие расстояния» от  i₀  до всех вершин на 0-шаговых путях

  for i in M do
    v[i] := INFINITY; by[i] := 0;
  od;
  v[i0] := 0;

Вектор by[M] будет использоваться для хранения информации о дугах, входящих в каждую вершину на оптимальных путях. Значение 0 соответствует отсутствию пути.

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

  bContinue := TRUE;
  while bContinue do
    SCAN_ALL_ARCS;
  od;

Булева переменная bContinue используется для управления внешним циклом, а псевдооператор SCAN_ALL_ARCS мы сейчас уточним.

SCAN_ALL_ARCS ≡
  bContinue := FALSE;
  for j in N do
    if v[iBeg(j)]+w[j] < v[iEnd(j)] then
      v[iEnd(j)] := v[iBeg(j)]+w[j]; by[iEnd(j)] := j;
      bContinue := TRUE;
    fi
  od;

Вот, собственно, и всё. Когда встречается дуга, у которой имеющийся путь от исходной вершины до начала выгодно использовать для построения пути до конца дуги, этим нужно воспользоваться. При этом в нужный элемент by[M] записывается эта дуга. Оптимальный путь до любой вершины строится «обратным ходом»

  PATH := EMPTY_PATH; iCur := i;
  while by[iCur] > 0 do
    PATH := concatenate(by[iCur],PATH);
    iCur := iBeg(by[iCur]);
  od;

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

Будем хранить отдельно множество вершин, у которых начались изменения v[i] и эти изменения еще могут происходить.

В соответствии с этой целью разобьем множество вершин на три подмножества
    M = M0∪M1∪M2,
где
  M0 — множество вершин, в которых v[i] вычислено окончательно,
  M1 — множество вершин, где изменения еще возможны,
  M2 — множество вершин, еще не затронутых алгоритмом.

Первоначально множество M0 пусто, M1 состоит из начальной вершины со значением v=0, остальные вершины находятся в M2.

Вычислительный процесс представляет собой цикл, который продолжается до тех пор, пока не исчерпается множество M1 (на каждой итерации из него одна вершина убирается, но множество может и пополняться), либо пока требуемая нам вершина не попадет в множество M0.

  bContinue := TRUE;
  while bContinue do
    bContinue := FALSE;
    SELECT_AND_TREATE_A_VERTEX;
  od;

Разберемся с выбором вершины в множестве M1 и ее обработкой

SELECT_AND_TREATE_A_VERTEX ≡
  i0 := VERTEX_IN_M1_with_MINIMAL_V;
  MOVE_FROM_M1_TO_M0(i0);
  SCAN_ARCS_EXITING_FROM(i0);

Как ищется в множестве M1 вершина с минимальным значением v, мы сейчас уточнять не будем — еще рано. И перевод этой вершины из одного множества в другое нас пока волновать не должен. Посмотрим, что происходит при просмотре дуг, выходящих из вершины i0. Пока отметим, что это просто цикл

SCAN_ARCS_EXITING_FROM(i0) ≡
  for j in EXIT_ARCS(i0) do
    TREATE_ARC(j)
  od;

и разберемся в теле цикла

TREATE_ARC(j) ≡
  iE := iEnd(j); v1 := v[i0]+w[j];
  if iE in M2 then MOVE_FROM_M2_TO_M1(iE,j,v1)
  else if (iE in M1) and (v[iE] > v1) then
    UPDATE_IN_M1(iE,v1,j)
  fi fi;

Поясним, что здесь делается. Если конец дуги j, который мы записали для удобства в переменную iE, находится еще в множестве M2, его обязательно нужно перевести в M1. Если же он находится в множестве M1, то нужно проверить, не улучшается ли путь, ведущий в iE, от использования дуги j. Если улучшается, то нужно сделать соответствующее исправление. Остальные случаи пропускаются — они никакой пользы не приносят.

Детали реализации оставшихся процедур зависят от выбранного представления данных. Об этом мы сейчас и будем говорить.

  MOVE_FROM_M2_TO_M1(iE,j,v1) — включение в множество
  UPDATE_IN_M1(iE,v1,j)       — изменение информации о вершине
  MOVE_FROM_M1_TO_M0(i0)      — удаление из множества (а перед этим еще поиск минимума)

Действий MOVE_FROM_M1_TO_M0 понадобится порядка |M|, действий MOVE_FROM_M2_TO_M1 столько же, действий UPDATE_IN_M1 порядка |N|-|M|. Но это — достаточно простые общие оценки. При выборе системы для представления множества M1 мы должны балансировать затраты на поиск минимума в этом множестве и затраты на поддержание удобного для этого поиска представления.

В прошлом семестре мы рассматривали специальные системы с операциями включения нового элемента и выборки элемента с минимальным приоритетом. Такие системы называются приоритетными очередями.

Здесь мы рассмотрим еще один вариант приоритетной очереди, использующий идею ведер (buckets).

В начальном изложении схема покажется наивной, нам нужно будет набраться терпения, эти «наивности» легко преодолеваются, и схема получается очень простой и эффективной. Итак, излагается наивная схема.

Будем считать все веса дуг w[j] целыми числами. Тогда целыми числами будут и расстояния до вершин v[i]. Каждому неотрицательному целому числу k сопоставим ведро— хранилище тех вершин, хоторые хранятся в множестве M1 и имеют расстояние k. Такое хранилище легко организуется с помощью цепного списка, причем нам особенно удобна стековая дисциплина хранения.

Операция добавления элемента очень проста: в нужное ведро добавляется новый элемент, он вставляется в начало соответствующего цепного списка.

Удаление элемента выполняется тоже просто, так как мы всегда будем удалять в цепном списке первый элемент.

Поиск минимума тоже прост: ведра просматриваются до нахождения непустого ведра. Этот просмотр ведется с продолжением, к опустевшим ведрам мы уже не возвращаемся.

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

Теперь займемся улучшениями схемы.

1. Ограничение числа ведер.

О бесконечном числе ведер мы говорили только для простоты. Число ведер легко ограничить. Именно, если положить
R = 1 +  max {w[j] | j}, то  R  ведер будет достаточно при повторном использовании опустошающихся ведер.

2. Предположение целочисленности весов.

Само предположение целочисленности не так уж страшно. В современных компьютерах нам могут встретиться целые числа. изменяющиеся в огромном диапазоне, и только что определенное число  R  нас не спасет — оно будет слишком велико. Во многих случаях ситуацию может исправить «укрупнение ведер» — каждое ведро можно предназначать не для одного значения v[i], а для диапазона значений.

В качестве размера диапазона подойдет любое число, не превосходящее r = min {w[j] | j}. Не гарантируется, что значения, попадающие в одно ведро, будут упорядочены. Но это и не требуется, разность значений v[i] в одном ведре слишком мала. Нужно только, чтобы были упорядочены записи, касающиеся одной и той же вершины. А это гарантируется стековой дисциплиной работы с ведром.

При использовании таких диапазонов количество необходимых ведер определяется как  1 + (R-1) / r.

3. Иерархические ведра.

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

Вот рабочая информация вычислительного процесса перед первой итерацией

Перед второй итерацией

Перед третьей итерацией

Перед четвертой итерацией

Перед пятой итерацией

Результат

Как в методе Дейкстры, множество вершин разбивается на три подмножества:
    M = M0∪M1∪M2,
с примерно тем же назначением. Единственное отличие в том, что перевод вершины из множества M1 в множество M0 может быть отменен.

Элементы множества M1 выстроены в очередь, и вершины, поступающие в в множество M1 из M2, ставятся в конец очереди. А перевод из M1 в M0 идет в порядке этой очереди, что может привести к нарушению оптимальности вычисляемых путей. Поэтому проверка дуг идет и для вершин, уже переведенных в M0, и если обнаружилась возможность улучшения, то такая вершина возвращается в множество M1. Однако, она ставится в начало очереди, — чтобы ускорить повторную обработку выходящих из нее дуг (этим и объясняется название метода).

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