anvaka
Option to have multiple paths
Is there a way to have an option to show at least 3 shortest paths for given nodes?
Looking for this as well, though the problem is that you'd have to somehow tell the graph to avoid minute variations. The graph has no way to know what constitutes a sufficiently unique path.
The best way to solve this is perhaps to tell the graph to avoid [array of nodes...] when path finding. That way, it's just a matter of running findPath 3 times with different avoidances.
- Alternatively, you can probably hack this by just adjusting the
weightof links every iteration offindPath
Would love to see a more elegant implementation though.
That's right! All you need to do to get this is:
- Find the shortest path
- Pick an edge in the shortest path an assign its weight to Infinity
- Go to step 1.
When you repeat second time the path will be different, as we've made one previous edge impassible.
A suggestion is to make a link "impassible" if the weight is set to "undefined".
I've tried setting it to MAX_SAFE_INTEGER. The problem is that when the pathfinding becomes impossible (e.g. you block off all the routes) with this method, the pathfinder will still treat MAX_SAFE_INTEGER as a number and return a path rather than failing.
This contradicts the mental model, leads to silent failures/bugs and is just more overhead to manage.
EDIT: I tried using Number.POSITIVE_INFINITY, when all the paths are blocked, it just returns the last Node instead of an array of nodes.