search

gonum / graph

Graph packages for the Go language [DEPRECATED]
250 stars 39 forks source link

DijkstraFrom: fix documentation + small algorithm improvement proposal #194

Closed juroland closed 7 years ago

juroland commented 7 years ago

The first commit changes complexity based on the reference provided in comments (i.e. http://www.cs.utexas.edu/ftp/techreports/tr07-54.pdf). The second one is a first proposal to reduce unnecessary work due to the use of duplicated nodes in the priority queue. Better alternatives could be discussed. What do you think about this ?

kortschak commented 7 years ago

This would be better as two PRs (can you please use kernel style commit messages - the bodies are good, but they should have a header line).

Do you have a provenance for the optimisation, or is it purely from your analysis - it partially invalidates the comment above, so it would be good to say where the optimisation is from in that comment as an addendum.

When these are merged, we need to have you added to A+C in gonum/license.

juroland commented 7 years ago

Yes, as you guessed, this optimization is only based on my analysis.

Ok for the two PRs with commit messages that use the kernel style. They will arrive shortly.