Outpost Navigation

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s