To generate a set of high-probability (low-cost) paths that are rich enough to explain observed reads, we compute for each vertex in the read graph the minimum cost st-path passing through it. Finding these paths is computationally fast. Indeed, we only need to compute two shortest-paths trees in G, one outgoing from s and one incoming into t; the shortest st-path passing through a vertex v is the concatenation of the shortest s v-and vt-paths.