Теория графов → Разбор Лабиринт 1
02 май
Для начала определим цель задачи: найти путь минимальной длины из одной точки в графе до другой. Теперь определим, что нам дано:
1. Ориентированный граф из N вершин и M ребер.
a. Дуги в графе могут иметь как положительные, так и отрицательные веса.
b. Граф может содержать циклы (как положительные, так и отрицательные)
c. Граф может быть не связным.
d. Между двумя вершинами может быть сколь угодно большое количество ребер.
e. Граф может содержать петли.
2. Начальная и конечная вершины – A и B.
3. Начальный баланс, необходимый для прохождения проходов – P.
a. Баланс не может быть отрицательным. Следовательно, нельзя пройти через проход при нехватке баланса.
За основу возьмем алгоритм Беллмана-Форда (Поиск минимального пути в графе с отрицательными дугами). Алгоритм состоит из двух частей:
1. Поиск минимальных путей содержащих максимум N-1 дуг, то есть, возможно, не содержащих отрицательных циклов.
2. Поиск отрицательных циклов в графе.
Для реализации первой части алгоритма будем использовать матрицу G[N][N], где элемент G[i][j] – максимальный баланс, оставшийся после прохождения из начальной вершины в i-ую с использованием максимум j дуг (равен -1, если до вершины нельзя дойти, используя j дуг). Естественно, для j = 0 G[A][0] = P, G[i!=A][0] = -1. Далее, N-1 раз перебираем все ребра в графе и проверяем, могут ли они увеличить путь для какой-либо вершины. Так как нужно перебирать все ребра, будем хранить их в массиве E[M][3], где E[i][0] – вершина-начало дуги, E[i][1] – вершина-конец дуги и E[i][2] – вес дуги. Получаем следующий цикл:
for i := 1 -> N-1 do begin
for j := 0 -> M-1 do begin
if (G[ E[j][0] ][ i-1 ] >= 0 and G[ E[j][0] ][ i-1 ] – E[j][2] >= 0) then
G[E[j][1]][i] = MAX(G[E[j][0]][i-1] – E[j][2], G[E[j][1]][i], G[E[j][1]][i-1]);
end;
end;
Вторая часть состоит в поиске отрицательных циклов. Для этого будем опять перебирать все ребра до тех пор, пока не прекратятся изменения. При этом если для какой-либо вершины баланс увеличился, значит, вершина находится в отрицательном цикле и для нее можно поставить баланс равный бесконечности:
boolean flag = true;
int[] last := copy_of_G[][N-1];
while (flag) begin
flag = false;
int[] new := copy_of_last;
for j := 0 -> M-1 do begin
if (last[ E[j][0] ] >= 0 and
last[ E[j][0] ] – E[j][2] >= 0) then
new[E[j][1]][i] = MIN(MAX(last[E[j][0]] – E[j][2], new[E[j][1]]), INFINITY);
end;
for i := 0 -> N-1 do begin
if (new[i] > last[i]) then begin
flag := true; new[i] := INFINITY;
end;
end;
last := copy_of_new;
end;
В конце концов, массив last содержит максимальный баланс для каждой вершины с учетом всех отрицательных циклов. А last[B] – результат, который нам нужен.