Make a graph of JPs (w/o Lagrange ones) with a path lengths between those that are in the same pair of systems. Recalculate those lengths every production cycle.
When you have to find a path - run for minimal number of jumps, continue this cycle with additional 3 iterations (memorizing paths), then calc distances for every path and find the shortest.
To use Lagrange JPs more accurate it's possible to get their positions for estimated time of jump into this system. The same with the last trajectory patch (JP to final target) if it's orbital target.
The task will be much easier without Lagrange JPs, and it's not the only problem with them.
They are inconsistent with overall JP narrative (they are visible and usable before JP theory researched!), they are easy and natural way to abuse AI with massive salvos and so on.
Maybe it worth to consider to replace them with static in-system potential JPs to stabilize, smth like 1/2^n distances between central body and every interstellar JP. Or just exterminate them, because not enough game value for too much problems.
As you mentioned above, to make the above work I would need Lagrange point locations at the point of arrival in-system, not at the point the journey begins. I could use fleet speed to work out the arrival point at the system, then use that time to run orbital movement forward to learn the LP locations. However, I can't pre-store that information as it would be different for each fleet in each system. Also, some fleets (tugs) may change their speed mid-journey so I would need to handle that too, plus other fleets may be spending time loading/unloading or using delay orders rather than moving so that needs to be handled too. 'Load until full' is even worse.
Someone else mentioned not checking a JP chain beyond finding a valid path, but unfortunately a) that isn't necessarily true because leaving the system and re-entering could be a shorter route to the destination than simply heading in-system from the first jump point. Secondly, I would still be checking all the other jump chains to their end, so I don't save much processing time.
Ultimately, it is all the edge cases that make this a lot more intensive that it might seem at first glance. I'm happy that the current system is right 95% of the time and I don't want to spend a lot of effort and processing power trying to get the extra few percent, especially when there are manual interventions available to the player.