Arzela-Ascoli for L_p-norm

The characterization of norm compactness in $L^p$: you want the Frechét-Kolmogorov theorem, usually stated for $X=\mathbb{R}^n$ and $Y:=\mathbb{R}$. The proof follows quite easily from Ascoli-Arzelà by mollification. You can find it on Haïm Brezis' Functional Analysis.

For your interest in a minimal $f$, you might want to read a beginners textbook on Sobolev-Spaces and the calculus of variations, especially on the direct method, which is all about this. The beginner-texts won't deal with metric graphs, but I am pretty sure that you can see how to generalize to this from the solution of the problem on intervals (or rather general domains in $\mathbb{R}^n$) that you will find there. Let me give you a short overview for $p>1$ (the case $p=1$ is a bit more tricky in the analysis and it turns out that any monotone function is a minimizer):

The direct method in a simple example

Let $I=[a,b]$ be an interval and consider the Sobolev-space $W^{1,p}(I;\mathbb{R})$, which is the closure of $C^1(I;\mathbb{R})$ in the norm

$$\|f\|^p_{W^{1,p}} = \|f'\|_{L^p}^p + \|f\|_{L^p}^p.$$

In general for every $f\in W^{1,p}(I,\mathbb{R})$, which you can approximate in the norm using smooth $(f_k)_k$, the weak-derivative $f' := \lim_{k\to\infty} f_k'$ is a well defined $L^p$ function. It won't be the pointwise derivative, but in many cases you can almost treat it as such. Furthermore one can prove that $W^{1,p}$ is a reflexive space (here $p>1$ is needed).

Now let's say, we are interested in the class of functions $A := \{f\in W^{1,p}: f(a) = 0, f(b)=1\}$. (One needs to make sure that $f(a)$ and $f(b)$ are well defined here, this is in fact due to the trace-theorem, that you will also find in any relevant text.) And we want to minimize $\|f'\|_p$ in this class. (This method is a bit of overkill for such a simple problem, where we could guess the solution.)

Then first we note that there is an obvious bound from below and so we can pick a sequence $(f_k)_k$ such that $\|f_k'\|_{L^p} \to \inf_{g\in A} \|g'\|_{L^p}$. In particular then $\|f_k'\|_{L^p}$ is bounded. Now we need the next tool which is Poincare's inequality, which due to $f_k(a) = 0$ (which prevents shifting by constants) also implies that $\|f_k\|_{W^{1,p}}$ is bounded.

But then there is the Banach-Alaoglu theorem, which is kind of the convergence theorem you were looking for. This tells us that $f_k$ has a weak* (=weak, since $W^{1,p}$ is reflexive) converging subsequence with some limit $f \in W^{1,p}(I;\mathbb{R})$.

Now finally using a bit more of the toolbox: The trace-theorem also shows that the boundary conditions are stable under weak convergence, so $f \in A$. And weak convergence of $f_k$ in $W^{1,p}$ means weak convergence of $f_k$ and $f_k'$ in $L^p$. Finally the norm is lower semi-continuous under weak convergence. There is no norm convergence as you requested in your question, but the point is that lower semicontinuity is enough, as we get

$$\inf_{g\in A} \|g'\|_{L^p} \leq \|f'\|_{L^p} \leq \liminf_{k\to\infty} \|f_k'\|_{L^p} = \inf_{g\in A} \|g'\|_{L^p}$$

So $f$ is indeed a minimizer in the class $A$. Now the final step would be to use the Euler-Lagrange equation to show that $f$ is in fact affine (which would translate to piecewise affine in you case).

However...

All this being said there might be another solution to your problem requiring far less hard analysis. In your metric graphs you only ever have to consider piecewise affine functions. Let $f:[a,b] \to Y$ be a map from an interval to a metric graph. Now for fixed $f(a),f(b)$ and a fixed path from $f(a)$ through the vertices $f(x_1) = p_1,..., f(x_n) = p_n$ to $f(b)$, the minimal $f$ is the piecewise affine one. Then since the set of $x_i$ with $a \leq x_1 \leq ... \leq x_n \leq b$ is compact and $\|f'\|_p$ continuous with respect to that choice, there is a minimal $x_1 < ... < x_n$ in there. Now there are finitely many loop free paths to choose in a finite graph, so there is a finite choice and thus a minimal $p_1,...,p_n$ as well. But then for any $f: X \to Y$, with $f(v_i)$ fixed on the vertices $v_i$, you'll get a minimal $f$ by applying the previous reasoning. And now since $Y$ is compact, and $\|f'\|_p$ should be continuous under the choice of $f(v_i)$, you'll get your minimizer. I'm no expert on metric graphs, but I am quite sure something like this has already been written down though.