In the lab I was told by a lab facilitator that it says that we DO NOT need to determine the fastest route but instead just "a valid path" to get full marks. Does this mean that if we return just any valid route we can still get full marks (and not wait for other potentially faster routes to come in).

It should ideally be the fastest route, can't say much for marking but if you can easily return the fastest route then you should do so.