p4: ¿qué campos necesito?

Necesitar, lo que se dice necesitar, sólo necesitas el grafo

private final Grafo grafo;

Salvo justificación muy justificada, dudo que necesites nada más.

En particular v0, destino y S deben ser variables locales de los métodos.