  Kantorovich distance (or 1-Wasserstein distance) on the probability simplex
of a finite metric space is the value of a Linear Programming problem for which
a closed-form expression is known in some cases. When the ground distance is
defined by a graph, a few examples have already been studied. In the present
paper, after re-deriving, with different tools, the result for trees, we prove
that, for an arbitrary weighted graph, the K-distance is the minimum of the
K-distances over all the spanning trees associated with the graph. We work in
the dual LP-problem by using Arens-Eells norm associated with the metric space.
Finally, we introduce new norms that are naturally related to
$\ell_1$-embeddable distances and allows for a partial extension of our results
to this new setting.
