Поиск всех путей между двумя вершинами ?

Всех путей - очень много, точнее, их количество неполиномиально. Поэтому применять здесь bfs/dfs бессмысленно, нужен обычный рекурсивный перебор. Впрочем, его легко получить из алгоритма dfs, убрав использование отметок посещённости вершин (т.е. теперь мы будем пытаться заходить во все вершины, а не только непосещённые).