Семинар 6.

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

2.	Нахождение кратчайшего пути в 1-k графе, то есть в графе, в котором рёбра
	имеют длины от 1 до k.
	Первый способ: разбиваем ребро длины l на l рёбер длины 1 (и добавляем l-1
	вершину). После этого у нас невзвешенный граф и мы пускаем обычный обход в
	ширину. Время: O(kE).
	Второй способ: каждую вершину разбиваем на k вершин, делаем из них цепочку.
	Все рёбра, исходившие из оригинальной вершины, исходят теперь из последней
	вершины нашей цепочки. А рёбра, входившие в вершину, распределяются так:
	длины 1 входят в последнюю вершину цепочки, длины 2 — в предпоследнюю,
	длины 3 — в пред-предпоследнюю, и так далее. Время: O(kV + E). Ускорение
	по сравнению с первым способом достигается за счёт того, что мы объединили
	вершины, в которых мы "ждём", когда приходим в вершину по ребру длины
	больше 1.

3.	Третий способ: создаём k+1 очередь. В нулевой очереди у нас будут лежать все
	вершины, до которых есть путь текущей длины l. Теперь мы будем (до)заполнять
	остальные k очередей, кладя в i-ю очередь вершины, до которых есть путь длины
	l + i. Для этого берём следующую вершину v из нулевой очереди. Если расстояние
	записанное в этой вершине меньше l, то существует путь до этой вершины меньшей
	длины и она была обработана ранее. В противном случае (расстояние в вершине
	равно l, а больше l оно быть не может), вершину нужно обработать сейчас. Для
	каждого соседа u нашей вершины v, сравниваем расстояние, записанное в нём
	с новым претендентом на расстояние: l + i, где i = длина ребра (v, u). Если
	новое расстояние меньше старого, то обновляем значение в вершине u и добавляем
	её в i-ю очередь. Иначе ничего не делаем.
	Когда нулевая очередь иссякает, мы увеличиваем текущее расстояние на единицу,
	а очереди сдвигаем на позицию меньшк. Будем продолжать эту процедуру пока у
	нас будут непустые очереди. Так как каждая вершина появляется в очереди только
	после перехода по какому-то ребру, то время работы алгоритма получится
	O(kV + E). Дополнительной памяти потребуется O(kV), так как каждая вершина
	побывает в каждой очереди максимум по одному разу.
	Заметим, что слагаемое kV в асимптотике появляется в основном из-за того,
	что нам может понадобиться просматривать большое число пустых очередей.
	Это даёт дальнейший простор для оптимизации. Однако смысла в этом мало,
	потому что при больших k лучше использовать алгоритм Дейкстры.

4.	Рассмотрим 0-1 граф, то есть граф, в котором все рёбра имеют вес 0 или 1.
	Пусть у нас есть вершина v, тогда мы любым обходом строим множество вершин,
	до которых расстояние от v равно нулю: при обходе мы идём только по нулевым
	рёбрам. Получив это множество, мы строим множество вершин, расстояние до
	которых от v равно 1 следующим образом: берём каждую вершину из нулевого
	множества, идём по всем единичным рёбрам, из результирующего множества
	вершин выбрасываем вершины, принадлежащие нулевому множеству. После этого,
	мы из получившегося множества делаем ещё один обход по нулевым рёбрам,
	ведущим в вершины не из нулевого множества. Добавив к стартовому единичному
	множеству все вершины, до которых мы смогли добраться, получим множество
	вершин, расстояние до которых равно 1. И так продолжаем дальше.

5.	Но лучше это делать по-другому. Сюда можно приспособить алгоритм, который
	мы использовали для 1-k графов. Единственное отличие состоит в том, что мы
	можем засовывать элементы в обрабатываемую очередь, но это не так важно.
	Итак, заведём дек, и если мы в данный момент обрабатываем вершину с
	расстоянием i, то можем получить только вершину с расстоянием i и i+1.
	В первом случае, мы запишем вершину в начало стека, во втором — в конец.
	Так же, как и раньше, у нас есть возможность поместить одну и ту же вершину
	в дек несколько раз. Это нужно учитывать так же как и раньше.

6.	Пусть мы хотим найти все рёбра, лежащие на каком-либо из минимальных путей
	из a в b. Эта задача решается двумя обходами в ширину: для каждой вершины x
	определяем длину минимального пути из a: d_a[x], и из b d_b[x]. Теперь
	критерий того, что ребро (u, v) лежит на каком-то минимальном пути:
	d_a[b] = d_a[u] + 1 + d_b[v].
	Аналогично, если нужно найти не рёбра, а такие вершины, то для вершины v
	критерием того что она лежит на каком-то минимальном пути будет равенство:
	d_a[v] + d_b[v] = d_a[b].