foo = {{a, b}, {c, d, e, f}, {x, y}};
foo = Map[ToString, {{a, b, c}, {f, g, h}, {u, v, x}, {r, s, t}}, {2}];
foo = Map[ToString, {{a, b, c}, {f, g, h}, {u, v, x}, {r, s, t}}, {2}];
foo = {{a, b}, {c, d, e, f}, {x, y}};
p = Partition[foo, 2, 1];
edgesList = Flatten[Outer[List, #[[1]], #[[2]]] & /@ p, 2];
edges = DirectedEdge @@@ edgesList;
Table[idxWeight[ss] = 1, {ss, edgesList}];
subSets = Subsets[foo, {2}];
allPairs = Flatten[Tuples /@ subSets, 1];
allEndToEnd = Tuples[{First@foo, Last@foo}];
kk = {};

ii = 0;
(* perturbation stack*)
pertStack = ConstantArray[{}, Length@allEndToEnd];
While[Union@Flatten[Subsets[#, {2}] & /@ kk, 1] != allPairs &&
   ii < 500,
  g = Graph[edges,
    EdgeWeight -> Table[idxWeight@ss, {ss, edgesList}]];
  sp = FindShortestPath[g,
    Sequence @@ allEndToEnd[[Mod[ii++, Length@allEndToEnd, 1]]]];
  pathEdges = Partition[sp, 2, 1];
  kk = Union[kk, {sp}];
  (idxWeight[#]++) & /@ Partition[sp, 2, 1];
  pertStack[[Mod[ii, Length@allEndToEnd, 1]]] = kk;
  If[Equal @@ pertStack,
   idxWeight[#]++ & /@ RandomChoice[edgesList, 3]];
  ];
kk