I give two algorithms. The first algorithm is basically a Frankenstein of breadth-first search and Dijkstra’s algorithm. The second algorithm is a recursive backtracking algorithm that performs a depth-first search through the graph that represents the outposts and roads.
The first algorithm is better. Recursive backtracking enumerates all possible solutions. In contrast, the first solution that breadth-first search finds is guaranteed to be the optimal solution. So, once it finds one solution, it can stop.