Description
Given the result of a single-source algorithm like Dijkstra or Bellman–Ford, provide a function which can extract the path from a given source to a given destination. Ideally, we should define a new object type for a shortest path tree that has the method to do so on it:
var shortestPathTree = graphlib.alg.dijkstra(g, "A", weight)
{weight, path} = shortestPathTree.path("A", "B")
console.log(weight, path)
The above should print two things: The weight of the path from A to B (which is literally shortestPathTree["B"].distance) as well as the path, which should be an array of nodes, in the correct order.
Alternatively, if we want to maintain the current data type returned by dijkstra for backwards compatibility, we could introduce a new function for path extraction:
var shortestPathTree = graphlib.alg.dijkstra(g, "A", weight)
{weight, path} = graphlib.extractPath(shortestPathTree, "A", "B")
console.log(weight, path)
The rationale for the above
5091
is that it is often the case that the application has to extract the shortest path between a source and a destination. While it is not a lot of work to traverse the predecessor pointers, it ends up being repetitive and we would rather avoid duplication by incorporating it in the library.
@pkakelas perhaps you can solve this by migrating our "getOptimalPath" code into a graphlib PR.