Thread: About path finding(in Graphs)..

Originally Posted by manasij7479

:Too much Calculation:
Though this can become ineffective if I try to manage subnets recursively....

I would think crunching numbers are faster than memory accesses. Anyway, don't throw the idea out the window before you actually see how it performs in real code.

I don't see much application for A* here, but if you're interested, take a look at A* search algorithm - Wikipedia, the free encyclopedia, particularly the Weighted A* section. That allows you to pick a heuristic that sometimes overestimates by a bit, resulting in faster but non-optimal paths. This shouldn't be a problem though, since you only need good enough. Your problem will be with devising a reasonable heuristic.

The IP address "distance" will not work as a heuristic for A*. For A* to be optimal, the heuristic must never overestimate the cost from any node to the goal. For spatial stuff, straight line is great, since it's the shortest possible distance between any two nodes. To do that, we require some sort of Cartesian coordinates for every node in the graph. We're looking the path with the shortest time, and there is no correlation between IP addresses and the latency between them. You would need something that guessed the fastest possible travel time between any node and the goal. That would have to account for the number of hops along the way, but the individual nodes don't know how far they are from the goal, so devising a valid heuristic is not really possible. We can't even make a reasonable guess as to how fast we can get from a node to the goal.

A little bit of Googling for "a algorithm for fastest times" (Google discards the *) turned up this paper, which might be a useful, if a little bit dry, read. It works with A*, so might have some useful heuristics to investigate.

EDIT: I judged that paper by the title and scanning the abstract, no idea how good it really is.