I wonder if we can solve the shortest-path with a space filling curve or is there a better solution? How good would be the approximation compared to an exact solver? The graph doesn't need to satisfy the triangle inequality.
A* with good heuristic function is generally the best solution (in terms of speed and finding shortest path).
I'm not sure what do you want to achieve with space-filling curve. I suppose it could give you interesting path in areas where costs are equal.