I happen to really like A-star search. So I'll give this a shot just for fun. Let Q[(Node, Cost)] be a priority queue. Let G be a graph. (This makes up the

I happen to really like A-star search. So I'll give this a shot just for fun. Let Q[(Node, Cost)] be a priority queue. Let G be a graph. (This makes up the search space.) Let V be the set of Nodes visited by the algorithm. Let S be the starting Node of G. Let F be the objective Node of G. (Node we are searching for) Let D(N1, N2) -> n be a function (computes the number of edges between N1 and N2. Let H(N) -> T be a function that computes an admissible heuristic cost for traversing N. (eg, taxicab distance) Let Search(G, Q, V, S, F) be a function that finds the lowest-cost path to F: Add (S, 0) to Q While there are items in Q: Pop (N, C) from Q If N is equal to F: Return the path from N to S. (Trivial parent traversal) Add N to V For each Nc in N's neighbours: Set Nc.Parent = N If Nc is not in V: Add (Nc, H(N) + D(N, Nc)) to Q Return an error, a path does not exist. I have to admit this ended up taking longer than I thought it would. ~20 minutes. And I'm not sure if it's correct.