[DOCUMENTATION | DELAYED] Explanation about ShortestPathOneToMany

[magnushiie]

What is your docs question about? Ask it I assumed ShortestPathOneToMany used some clever algorithmic trick (like unidirectional Dijkstra is able to calculate all targets for one source in one go). Now, having read the algorithm source code, it seems to be almost the same as executing ShortestPathOneOne for all targets in sequence. The only difference I can see is that it is reusing the data structures across iterations. Is it only about reducing allocations or is there some deeper optimization that I cannot spot?

What do you suggest? Add a section to README about how ShortestPathOneToMany works and why it is faster.

Additional context None

[LdDl]

There is no clever trick. This is all about just reducing amount of allocations as you noticed.

reusing the data structures across iterations

Yes. It's just used in relaxation functions and nothing special:

// ...
// cid - ID of queue for certain target node
if forwProcessed[temp] != cid || queryDist[temp] > alt {
  queryDist[temp] = alt
  prev[temp] = vertex.id
  forwProcessed[temp] = cid
  node := &bidirectionalVertex{
      id:        temp,
      queryDist: alt,
  }
  heap.Push(forwQ, node)
}
// ...

We are not planning to make section about this function currently, since it's not a big optimization (at all, lol). When we have some really useful optimization we'll make docs for it for sure.

Marking this issue as delayed for now