In situations with a fixed starting vertex and a number of different target vertices, calling ShortestPath for all of these vertices is quite expensive. Because ShortestPath already computes the cost of reaching a vertex from the start for all vertices in the graph, the algorithm can possibly easily be optimized for multiple targets.
This should be implemented in a new function ShortestPaths[K comparable, T any](g Graph[K, T], source K, targets ...K) ([][]K, error) where [n][]K contains the vertex hashes of the shortest path for targets[n].
The difference to the current implementation is that the backtracking needs to be performed for all target vertices.
In situations with a fixed starting vertex and a number of different target vertices, calling
ShortestPathfor all of these vertices is quite expensive. BecauseShortestPathalready computes the cost of reaching a vertex from the start for all vertices in the graph, the algorithm can possibly easily be optimized for multiple targets.This should be implemented in a new function
ShortestPaths[K comparable, T any](g Graph[K, T], source K, targets ...K) ([][]K, error)where[n][]Kcontains the vertex hashes of the shortest path fortargets[n].The difference to the current implementation is that the backtracking needs to be performed for all target vertices.
https://github.com/dominikbraun/graph/blob/f1f0bea0dbf1b32c14d961af033e3bf1234ae7fc/paths.go#L130-L142