  Highly dynamic networks rarely offer end-to-end connectivity at a given time.
Yet, connectivity in these networks can be established over time and space,
based on temporal analogues of multi-hop paths (also called {\em journeys}).
Attempting to optimize the selection of the journeys in these networks
naturally leads to the study of three cases: shortest (minimum hop), fastest
(minimum duration), and foremost (earliest arrival) journeys. Efficient
centralized algorithms exists to compute all cases, when the full knowledge of
the network evolution is given.
  In this paper, we study the {\em distributed} counterparts of these problems,
i.e. shortest, fastest, and foremost broadcast with termination detection
(TDB), with minimal knowledge on the topology.
  We show that the feasibility of each of these problems requires distinct
features on the evolution, through identifying three classes of dynamic graphs
wherein the problems become gradually feasible: graphs in which the
re-appearance of edges is {\em recurrent} (class R), {\em bounded-recurrent}
(B), or {\em periodic} (P), together with specific knowledge that are
respectively $n$ (the number of nodes), $\Delta$ (a bound on the recurrence
time), and $p$ (the period). In these classes it is not required that all pairs
of nodes get in contact -- only that the overall {\em footprint} of the graph
is connected over time.
  Our results, together with the strict inclusion between $P$, $B$, and $R$,
implies a feasibility order among the three variants of the problem, i.e.
TDB[foremost] requires weaker assumptions on the topology dynamics than
TDB[shortest], which itself requires less than TDB[fastest]. Reversely, these
differences in feasibility imply that the computational powers of $R_n$,
$B_\Delta$, and $P_p$ also form a strict hierarchy.
