Outpost Navigation is an ACM-ICPC problem. I solved it about a month ago, and my algorithms are up at my GitHub.

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.

### Like this:

Like Loading...

*Related*