Thanks for any ideas beforehand, I am quite new to graph algorithms and love this library for it’s speed and flexibility.
Problem: I am trying to do a search using A* search on an implicit graph using AStarVisitor. My goal however is to search for all paths (until some depth limit or max number of paths) rather than stopping at the first path found. All paths can include both extremely diverse paths and paths that share edges amongst themselves. These are graphs are anywhere between 250k vertices & 5M edges.
Tried Idea: I tried to do this by playing around with the cost of a vertex & weight of the edges in the paths already found, but got nowhere by doing additive penalising of costs and weight to force exploration. I suspect, I might be doing the updates wrong. This was suggested by multiple LRMs, so thought of trying it out first.
Questions:
- Is A* search even a good idea if you want to repeatedly search on an implicit graph for diverse paths? Is the idea of playing around with edge weights and vertex costs even a sane idea?
- If above is feasible, can anyone point to any literature that talks about how to these updates for repeated searches
- Are there any other ways using graph tool library that I am missing here?
- Is there a name for this sort of repeated searching in graph theory that I can read up on?
Note: Computing all paths by constructing an explicit graph is way too slow for my use-case, and prefer to keep the graph implicit.