Поиск в ширину: необычные графы, построение
Поиск в ширину: 12-графы, 01-графы, вещественые веса и несколько очередей
Ford-Bellman: кратчайшие пути в произвольном графе
Дейкстра и дерево отрезков
Еще задачи на dfs