Reworked the approx-SP tree stuff to clobber two big hot spots:
1 - Moved edge relaxation from the lower-bound check, where it fires hundreds or more times per route, to the tree-update, which fires at most once per route.
2 - Resurrected exhausted-edge idea, where edge updates that can't trip an update prima facie are not even queued for update, where they would simply have to be checked and chucked out again.
Additionally:
Heuristic values are bumped up by 0.5%, to nudge pathfinding to prefer nodes closer to the target node.
With these changes, Reft sector plus the sectors orthogonal to it go from taking 272 s overall (184 s pathfinding) to 228 s (152 s pathfinding) on my current box.
Thanks to @GamesByDavidE for help wringing out the edge-relaxation changes.
Reworked the approx-SP tree stuff to clobber two big hot spots:
1 - Moved edge relaxation from the lower-bound check, where it fires hundreds or more times per route, to the tree-update, which fires at most once per route. 2 - Resurrected exhausted-edge idea, where edge updates that can't trip an update prima facie are not even queued for update, where they would simply have to be checked and chucked out again.
Additionally: Heuristic values are bumped up by 0.5%, to nudge pathfinding to prefer nodes closer to the target node.
With these changes, Reft sector plus the sectors orthogonal to it go from taking 272 s overall (184 s pathfinding) to 228 s (152 s pathfinding) on my current box.
Thanks to @GamesByDavidE for help wringing out the edge-relaxation changes.