graph - Dijkstra-based algorithm optimization for caching -

i need find optimal path connecting 2 planar points. i'm given function determines maximal advance velocity, depends on both location , time.

my solution based on dijkstra algorithm. @ first cover plane 2d lattice, considering discrete points. points connected neighbors specified order, sufficient direction resolution. find best path (sort of) dijkstra algorithm. next improve resolution/quality of found path. increase lattice density , neighbor connectivity order, restricting search points close enough already-found path. may repeated until needed resolution achieved.

this works well, nevertheless i'd improve overall algorithm performance. i've implemented several tricks, such variable lattice density , neighbor connectivity order, based on "smoothness" of price function. believe there's potential improve dijkstra algorithm (applicable specific graph), couldn't realize yet.

first let's agree on terminology. split lattice points 3 categories:

• cold - points have not been reached algorithm.
• warm - points reached, not processed yet (i.e. have potential improvement)
• stable - points processed.

at each step dijkstra algorithm picks "cheapest" warm lattice point, , tries improve price of neighbors. because of nature of graph, kind of cloud of stable points, surrounded thin layer of warm points. @ each step warm point @ cloud perimeter processed, it's added stable cloud, , warm perimeter (potentially) expanded.

the problem warm points consequently processed algorithm spatially (hence - topologically) unrelated. typical warm perimeter consists of hundreds of thousands of points. @ each step next warm point process pseudo-randomal (spatially), hence there's virtually no chance 2 related points processed 1 after another.

this indeed creates problem cpu cache utilization. @ each step cpu deals pseudo-random memory location. since there's large amount of warm points - relevant data may not fit cpu cache (it's order of tens hundreds of mb).

well, indeed implication of dijkstra algorithm. whole idea explicitly pick cheapest warm point, regardless other properties.

however intuitively it's obvious points on 1 side of big cloud perimeter don't make sense points on side (in our specific case), , there's no problem swap processing order.

hence though ways of "adjusting" warm points processing order, yet without compromising algorithm in general. thought several ideas, such diving plane blocks, , partially solving them independently until criteria met, meaning solution may interfered. or alternatively ignore interference, , potentially allow "re-solving" (i.e. transition stable warm).

however far not find rigorous method.

are there ideas how this? perhaps it's know problem, existing research , (hopefully) solutions?

thanks in advance. , sorry long question.

what you're describing motivation behind a* search algorithm, modification of dijkstra's algorithm can dramatically improve runtime guiding search in direction pick points keep getting closer , closer destination. a* never more work naive dijkstra's implementation, , typically tends expand out nodes clustered on frontier of warm nodes closest destination node.

internally, a* works augmenting dijkstra's algorithm heuristic function estimates remaining distance target node. means if can rough approximation of how far away given node destination, can end ignoring nodes don't need processed in favor of nodes better.

a* not designed cache-optimal algorithm, believe increase in speed due to

1. expanding fewer nodes (less in cache), and
2. expanding nodes closer goal (which processed more , more in cache)

will give huge performance increase , better cache performance.

hope helps!