The Cable-Trench Problem (CTP) is defined as a combination of the Shortest Path and Minimum Spanning Tree Problems. Specifically, let G ¼ ðÞ V; E be a connected weighted graph with specified vertex v1 2 V (referred to as the root), length leð Þ 0 for each e 2 E, and positive parameters τ and γ. The Cable-Trench Problem is the problem of finding, for given values of τ and γ, a spanning tree T of G such that τlτ ð Þþ T γlγ ðÞ T is minimized, where lτ ðÞ T is the total length of the spanning tree T, and lγ ðÞ T is the total path length in T from v1 to all other vertices ofV. Consider the ratio R= τ/γ. For R large enough, the solution will be a minimum spanning tree, and for R small enough, the solution will be a shortest path. This is the first article to present a methodology that iteratively uses integer programming software (CPLEX in this article) to efficiently generate all optimal spanning trees (GEAOST) for a CTP (for all values of R). An example will illustrate how sensitive the spanning trees solution can be to small changes in edge lengths. Also, GEAOST will be used to generate all optimal spanning trees for graphs based on a real-world radio astronomy application. How the sequence of all optimal spanning trees can be used for sensitivity analysis will be demonstrated.