Reischl, MaximilianKnauer, ChristianGuthe, MichaelLee, Sung-hee and Zollmann, Stefanie and Okabe, Makoto and Wuensche, Burkhard2020-10-292020-10-292020978-3-03868-120-5https://doi.org/10.2312/pg.20201228https://diglib.eg.org:443/handle/10.2312/pg20201228We present a new approach for path finding in weighted graphs using pre-computed minimal distance fields. By selecting the most promising minimal distance field at any given node and switching between them, our algorithm tries to find the shortest path. As we show, this approach scales very well for different topologies, hardware and graph sizes and has a mean length error below 1% while using reasonable amounts of memory. By keeping a simple structure and minimal backtracking, we are able to use the same approach on the massively parallel GPU, reducing the run time even further.Theory of computationGraph algorithms analysisComputational geometryMathematics of computingGraph algorithms10.2312/pg.2020122837-42