Описание алгоритма

Этот алгоритм строит кратчайшее дерево путей в ориентированном графе. Задача заключается в следующем, дан граф G, для каждой его дуги определено L[i] > 0 - ее длина (или вес). Надо найти ориентированное дерево с корнем в некоторой вершине i0, такое что SiL[i] - минимальна, где i пробегает все ребра, вошедшие в найденное дерево. Важно отметить, что минимальной должна быть именно сумма всех длин, а не длина путей от вершины i до остальных вершин.

Описание алгоритма:
Обозначим исходный граф G0<V0,E0>.

  1. Производим операцию спуска до нуля для длин всех дуг, входящих в каждую вершину, кроме вершины i0, то есть длины всех дуг, входящих в вершину уменьшаем на d = min{L[i]}, где i пробегает все дуги, входящие в данную вершину.
  2. Строим частичный граф с вершинами исходного, и взяв по одной дуге нулевой длины для каждой вершины, кроме i0. Обозначим этот граф как H0<V0,F0>.
  3. Если полученный граф H0 окажется деревом, то это дерево и есть искомое, и задача решена.
  4. В противном случае строим конденсацию графа H0. Обозначим ее D0<V1,F0>. F0 состоит из дуг H0, соединяющих вершины из V1 и обладающих минимальной длиной.
  5. Соединяем вершины из V0, содержащиеся в одной компоненте сильной связности, в одну. Затем склеиваем все дуги, соединяющие две такие "крупные" вершины в одну, и приписываем ей длину, равную минимальной длине всех склеиваемых дуг. Получаем новый граф G1<V1,E1>, содержащий заведемо меньше вершин, чем G0.
  6. К полученному графу G1 применим тот же набор действий. Через конечное число итераций мы построим ориентированное дерево Tk в некотором графе Gk.
  7. Обратный ход осуществляется следующим образом: вершина графа Gk заменяется сильно связанной компонентой из графа Gk-1. Затем в этой компоненте строим дерево из вершины, в которую входит дуга из другой компоненты сильной связности графа Gk-1.
  8. Таким образом построим и искомое дерево T0.