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