I am building a website where the user can only enter two points within an OSM map. Next what I need is to calculate ALL (I really mean all, even those that are unnecessarily far apart) possible paths between them taking into account the following: -taking into account that the various "nodes" of osm are connected to each other(I will not take into account one way directions etc, I will default that all routes can be done in both directions) I would then define the ACYCLE graph, so in the calculation if the next node has already been visited I discard that route to avoid loops or passing the same point again; -the calculation of possible routes will have a maximum length (e.g. "find all possible routes from a to b within 7 km" will give routes of 5-6 km even if a and b are 1 km apart); In the end I need to get an array of possible routes, with related altimetry etc. in such a way as to decide which of these to keep...
UPDATE 1: I was able to create an algorithm that, after converting the nodes of the OSM map into a graph, could find all the possible paths of ONE SMALL AREA and then pick the one with the highest elevation gain, the problem is that such a solution with thousands of nodes takes hours... So I chose to use algorithms like A* and Dijkstra with heuristics based on the elevation difference between nodes BUT unfortunately as predicted I ended up with a problem I called "the bridge trap": basically I selected two points on the map of which I already knew the route with the maximum elevation between the two of them; the initial point is close to a bridge (or equivalently a simple slope). I have noticed that the use of these algorithms, with their heuristics, as they are made, favour the path that immediately 'brings an advantage' (elevation in this case), leaving aside other paths that are an ENORMOUSLY better answer for the purpose. In fact, because of this, if the algorithm had not executed that bridge, it would have obtained a route with a much better elevation gain, and unfortunately this is not good since I want the route with the absolute best elevation gain. Other times it simply indicated the shortest way to node B when in fact there were ups and downs (thus more elevation build-up) that were not selected by heuristics because these involved first going down (low heuristic score) and THEN going up... Do you have any ideas for me to take into account the 'alternatives' that could lead to a better result? Thank you very much!