This is wrong or at least misleading in a couple of ways:
A* is not limited to point-to-point, it also handles point-to-set-of-points just fine (you just might have to reverse the direction you're thinking in). Although this is most often used for "we only need a path to one of them", it's still faster even if you need a path to all of them due to merging. Visiting all points (as BFS does) on the graph is rarely what you actually want (though admittedly, if you're able to throw away the grid it becomes more likely; like the article, I do find people use grids far too often).
BFS works just fine with variable edge weights, you just have to use a priority queue instead of a plain queue for the next set of nodes to be visited.
BFS with priority queue isn't BFS it's called Dijkstra's algorithm.
Are you sure it works correctly for shortest path to all points in set not just "we need one of them" case? When running in reverse I would expect closest point to be priotized first, which would potentially mark all the area around target as visited thus blocking paths from other points in set from reaching it. It's equivalent to introducing one more point in graph and connecting it to all the points in set. Unless it works for one to all in set it's a weaker result than what Dijkstra or BFS answers. If your problem doesn't need it, don't use it. But that's my point use the weakest algorithm which directly answers required query, and be aware that building more powerful algorithm by repeatedly calling more specialized but weaker one won't always be optimal.
A* can be tweaked to solve one-to-many shortest paths. You need to be careful about how you aggregate the heuristic function over all the targets [0]. Also, the performance improvements vs Dijkstra would practically disappear in many scenarios, for example if your source is "in the middle" of all the targets. In that case there's no benefit to biasing your search towards any particular target: you might as well simply expand outwards as you do in ordinary Dijkstra.
For road network routing (which is more my thing) you are orders of magnitude better off pre-processing the graph with contraction heirarchies [1] and then using a specialised algorithm such as RPhast [2] at query time.
BFS works just fine with variable edge weights, you just have to use a priority queue instead of a plain queue for the next set of nodes to be visited.
But usually you don't call it BFS if it's using a priority queue?
Comments
This is wrong or at least misleading in a couple of ways:
A* is not limited to point-to-point, it also handles point-to-set-of-points just fine (you just might have to reverse the direction you're thinking in). Although this is most often used for "we only need a path to one of them", it's still faster even if you need a path to all of them due to merging. Visiting all points (as BFS does) on the graph is rarely what you actually want (though admittedly, if you're able to throw away the grid it becomes more likely; like the article, I do find people use grids far too often).
BFS works just fine with variable edge weights, you just have to use a priority queue instead of a plain queue for the next set of nodes to be visited.
BFS with priority queue isn't BFS it's called Dijkstra's algorithm.
Are you sure it works correctly for shortest path to all points in set not just "we need one of them" case? When running in reverse I would expect closest point to be priotized first, which would potentially mark all the area around target as visited thus blocking paths from other points in set from reaching it. It's equivalent to introducing one more point in graph and connecting it to all the points in set. Unless it works for one to all in set it's a weaker result than what Dijkstra or BFS answers. If your problem doesn't need it, don't use it. But that's my point use the weakest algorithm which directly answers required query, and be aware that building more powerful algorithm by repeatedly calling more specialized but weaker one won't always be optimal.
A* can be tweaked to solve one-to-many shortest paths. You need to be careful about how you aggregate the heuristic function over all the targets [0]. Also, the performance improvements vs Dijkstra would practically disappear in many scenarios, for example if your source is "in the middle" of all the targets. In that case there's no benefit to biasing your search towards any particular target: you might as well simply expand outwards as you do in ordinary Dijkstra.
For road network routing (which is more my thing) you are orders of magnitude better off pre-processing the graph with contraction heirarchies [1] and then using a specialised algorithm such as RPhast [2] at query time.
[0] https://www.semanticscholar.org/paper/Heuristic-search-for-o...
[1] https://en.wikipedia.org/wiki/Contraction_hierarchies
[2] https://www.microsoft.com/en-us/research/publication/faster-...
But usually you don't call it BFS if it's using a priority queue?