Efficient pathfinding without heuristics?

Part of my program is a variable-sized set of Star Systems randomly linked by Warp Points. I have an A algorithm working rather well in the grid, but the random warp point links mean that even though the systems have X,Y coordinates for where they're located on a galactic map, a system at 2,3 isn't always linked directly to a system at 2,4 and so the shortest path may actually lead away from the target before it heads back towards it. I think this limitation eliminates A since there's almost no way to get a good heuristic figured out.

What I've done instead is a recursive node search (I believe this specific pattern is a Depth-First Search), and while it gets the job done, it also evaluates every possible path in the entire network of systems and warp points, so I'm worried it will run very slowly on larger sets of systems. My test data is 11 systems with 1-4 warp points each, and it averages over 700 node recursions for any non-adjacent path.

My knowledge of search/pathfinding algorithms is limited, but surely there's a way to not search every single node without needing to calculate a heuristic, or at least is there a heuristic here I'm not seeing?

Here's my code so far:

```
private int getNextSystem(StarSystem currentSystem, StarSystem targetSystem,
List pathVisited)
{
// If we're in the target system, stop recursion and
// start counting backwards for comparison to other paths
if (currentSystem == targetSystem)
return 0;

// Arbitrary number higher than maximum count of StarSystems
int countOfJumps = 99;
StarSystem bestSystem = currentSystem;

foreach (StarSystem system in currentSystem.GetConnectedStarSystems()
.Where(f=>!pathVisited.Contains(f)))
{
// I re-create the path list for each node-path so
// that it doesn't modify the source list by reference
// and mess up other node-paths
List newPath = new List();
for

Complete and Incomplete Algorithms

Search algorithms can be classed into two categories: complete and incomplete.

A complete algorithm will always succeed in finding what your searching for. And not surprisingly an incomplete algorithm may not always find your target node.

For arbitrary connected graphs, without any a priori knowledge of the graph topology a complete algorithm may be forced to visit all nodes. But may find your sought for node before visiting all nodes. A* is a complete best-first method with a heuristic to try to avoid searching unlikely parts of the graph unless absolutely necessary.

So unfortunately you can not guarantee that you will never visit all nodes whatever algorithm you choose. But you can reduce the likelihood of that happening.

Without pre-processing

If you cannot consider pre-processing your graph then you're stuck with a myriad of on-line algorithms such as depth-first, breadth-first, A and greedy-best-first. Out of the bunch I'd bet on A in most cases if the heuristic is even half good and the graphs are non-trivial.

If you expect all routes to be short, a breadth-first algorithm with cycle detection and duplicate node removal may outperform A* with a poor heuristic. I wouldn't bet on it though, you need to evaluate.

With pre-processing

In your case I'd see if I could pre-process the graph, even if you need to repeatedly re-do the pre-processing when the graph changes as long as you do sufficiently many searches between pre-processing it would be worth it.

You should look up Floyd-Warshall (or some derivative) and calculate the pairwise cost/distance/jumps between all nodes and use this table as a heuristic for your A. This heuristic will not only be admissible, it will be exact and your A search will complete in no-time.

Unless you of course modify the algorithm to store all pairwise routes as they are detected in a matrix of vectors, then you have O(1) run time at the cost of memory.

StackExchange Code Review Q#44584, answer score: 13