Is there any useful structure associated with the following instance of the Set Covering problem?

Let $G$ be a weighted graph and let $\mathcal{P}$ denote the set of all shortest paths between all pairs of nodes in $G$.  Construct an instance of set cover in which each element $e_i$ is associated with a path $P_i$ in $\mathcal{P}$, and each set $S_j$ is associated with a node $n_j$ in $G$, and $S_j$ contains precisely those elements $e_i$ such that $P_i$ contains $n_j$.

Does anything change if $\mathcal{P}$ consists of *all* paths in $G$?