title: A star search: a lot of nodes and a "slow" CheckLink between nodes... any suggestions?
body: <p>I'm facing an optimization problem:</p>
  
  <p>I've a graph with a lot of nodes (10^5) that represents points on a plane surface.</p>
  
  <p>I need to find the shortest path on the graph in order to reach the "end node", starting from the "start node".</p>
  
  <p>any pair of nodes can be connected or not. Checking if they are connected is a very costly operation. If they are connected, the weight associated to the link is the euclidean distance between the two nodes.</p>
  
  <p>At the moment I'm only checking all links from the "current node" to every other node, in order to fill the "open list" for A*. I chose A*, beacuse it seems the best algorithm in pathfinding and I've a fast, admissible and easy heuristic H for a node J (H = distance to the goal) but I'm not sure it's good for my problem.</p>
  
  <p>Building the graph up front is unmanageable, N^2 links needs to be checked, it's too slow. At the moment (almst) the entire graph is built only if there's no solution, no path from the beginning to the end.</p>
  
  <p>I'd like a hint for a better solution... thank you!</p>