bfs
[link]
0-1-bfs
Условие:
Каждое ребро графа имеет вес - 0 или 1, нужно найти кратчайший путь из S в T
Решение:
Используем Дэк (dequeue).
Если мы пришли в v по 0-ребру, добавляем ее в начало дэка, если по 1-ребру - в конец
Реализация:
инициализация очереди: int head = N, tail = N, q[2 * N];
добавить в начало: q[--head] = v
добавить в конец: q[tail++] = v
1-k-bfs
Условие:
Каждое ребро графа имеет вес - 1, 2, 3 ... k, нужно найти кратчайший путь из S в T
Решение:
Ребро веса 3 = путь из 3 ребер.
Время работы = Θ(E*k)
Реализация:
Сперва перестраиваем граф (добавляем промежуточные вершины)
Пускаем обычный bfs