Para la implementación puedes usar "
Sencilla implementación de grafos" o puedes usar otra librería.
Ahora para todos los caminos pueden usar backtracking que creo que sería la opción mas directa pero probablemente la menos optima.
El backtrack lo puedes implementar usando búsqueda a lo profundo (DFS) pero obviamente modificando el algoritmo.
También puede que exista un numero infinito de caminos en caso de que tu grafo tenga un ciclo.
Buena suerte con tu tarea.