Make ShortestPath faster

[amwolff]

I noticed that the performance of ShortestPath can be substantially improved. Instead of finding all the shortest paths from the initial vertex, we could terminate the search as soon as we found the path to the destination vertex.

I've opened a pull request because I already have a patch.

1. No API changes whatsoever;
2. This performance enhancement is based on the original E. W. Dijkstra's paper (it's what should be found in a CS textbook).

old/new comparison:

benchmark                       old ns/op     new ns/op     delta
BenchmarkShortestPath250-4      55089         31078         -43.59%
BenchmarkShortestPath500-4      121956        51563         -57.72%
BenchmarkShortestPath1000-4     206507        79512         -61.50%

[korthaj]

Artur, thanks a lot for the patch! I will certainly add this. However, I'm, really busy right now so it might take a few weeks.

On Wed, Oct 30, 2019 at 10:18 PM Artur M. Wolff [email protected] wrote:

I noticed that the performance of ShortestPath can be substantially improved. Instead of finding all shortest paths from the initial vertex, then picking the shortest path between v and w we want, we could terminate the search as soon as we found the path to the desired vertex.

I've opened a pull request, because I already have a patch.

1. No API changes whatsoever;
2. This performance enhancement is based on the original E. W. Dijkstra's paper (it's what should be found in a CS textbook).

old/new comparison:

benchmark old ns/op new ns/op delta BenchmarkShortestPath250-4 55089 31078 -43.59% BenchmarkShortestPath500-4 121956 51563 -57.72% BenchmarkShortestPath1000-4 206507 79512 -61.50%

---

You can view, comment on, or merge this pull request online at:

https://github.com/yourbasic/graph/pull/7 Commit Summary

• Make ShortestPath faster

File Changes

• M path.go https://github.com/yourbasic/graph/pull/7/files#diff-0 (51)
• M path_test.go https://github.com/yourbasic/graph/pull/7/files#diff-1 (66)

Patch Links:

• https://github.com/yourbasic/graph/pull/7.patch
• https://github.com/yourbasic/graph/pull/7.diff

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/yourbasic/graph/pull/7?email_source=notifications&email_token=ACVN3SZLBXKYSWNXMPOUVN3QRH2ZBA5CNFSM4JHAPC3KYY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4HVSDIHQ, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACVN3S5ULMPF6WB3UYYPOP3QRH2ZBANCNFSM4JHAPC3A .

[amwolff]

No problem! Let me know if you happen to have any questions regarding the patch.

[amwolff]

I was going through my old contributions and realized I made a mistake here in the comment about ShortestPath (it should be kept original). I've fixed this in case this may get merged. :)