A* heuristics for when no node coordinates are available

Question

Scenario:

Suppose I have a large pseudorandom graph complete with edge weights, but without any coordinate information associated with the nodes. In addition, there are N waypoints evenly distributed around the graph, containing precomputed shortest path information from each waypoint to every other node.

Goal:

Find the shortest path between a random source and target node.

From previous problems I've solved using A* and what papers I've read on the subject, heuristics often seem to rely on euclidian metrics for computing good distance approximation, e.g. a straight line.

My question is therefore: is there any ok heuristic that can help me solve the above scenario, or am I forced to rely on pure Dijkstra's algorithm (combined with the precomputed waypoint nodes)?

Any ideas or comments will be greatly appreciated.

EDIT

Thanks to all of you who helped out, utilizing the triangle inequality did the trick. The nearest waypoint computation is quite expensive so the average runtime compared to pure Dijkstra is considerably higher, but this is of really no importance at this point in time.

Here's an overview over the number of explored nodes (random source/target for each graph type):

The first graph type (1) consists of about 200 nodes and 250 edges, while the last graph type (40) consists of about 8000 nodes and 10000 edges (higher type means larger graph).

Answer 1

We want an optimistic heuristic for length of the shortest path from A to B.

Find the nearest waypoint to A. Call it W.

Then max { d(W,B) - d(W,A), 0 } is a lower bound on the length of the shortest path from A to B.

Proof:

By the triangle inequality we have d(W,B) ≤ d(W,A) + d(A,B).

Thus d(A,B) ≥ d(W,B) - d(W,A).

You could apply this idea symmetrically as well to get a slightly better bound. That is, find the nearest waypoint WA to A and the nearest waypoint WB to B and then your lower bound is

max { d(WA,B) - d(WA,A), d(WB,A) - d(WB,B), 0 }

What is nice about this heuristic is that it clearly improves as the density of waypoints increases.

Answer 2

Your heuristic can be:

shortest path distance between source and closest waypoint +
shortest path distance from that waypoint to your target node

EDIT

As Niklas has pointed out, this heuristic is not admissible. Therefore, it cannot be used in A*. Please disregard.