First I'd eleminate useless archs (A,A) and/or forbid them (by table rule).

Then I'd start with creating some meta data, like:

- Storing search results (known paths).

Why search what was already found?

- Storing information about how much cost (steps) it takes from node A to B (if known from a result).

That is the limit for the depth level of a recursive search for a better path.

- Is there any connection between node A and B?

This helps having a short response time for searches with no result.

- How many arches go from node A to any other nodes?

Nodes with many neighbors may be good candidates for a search with an intermediate node, which splits a search for a path from from A to B to two searches for a path from A to C and C to B.

- Cluster the graph to several subgraphs starting from each node and including only other nodes reachable with a certain (low) number of steps/cost.

Helps to have a maximum estimate for costs of subresults.

- Storing for each node, where you should go (if known) next when you finally want to reach node B.

Will route you automatically to your goal.

Maybe there is additional information like some sort of geometrical position of a node, so you may have an estimate for the distance. That may also help finding good candidates for intermediate nodes on your path.

Some of this data could be updated when adding or deleting a node or arch, some may need nightly builds of some datawarehouse.

Bye, Olaf.