Dijkstra O(N^2)

[yanpozka]

Hey man, good job, I just detected that your Go implementation of Dijkstra algorithms is O(N^2)
https://github.com/gyuho/learn/tree/master/doc/go_graph_shortest_path#dijkstra-algorithm

So the issue is that you have a O(N logN) solution in your description but in your Golang implementation if you include heap.Init(...) inside the loop:
for minHeap.Len() != 0
you'll have a N^2 time because the method heap.Init() has a time of O(N) so that call is inside of a O(N) loop.

Happy coding !!

[gyuho]

Great catch. I will update the code, which I believe I only need to heapify once after the for-loop.
The code is from https://github.com/gyuho/goraph.
I will test the code and commit to this repo as well.

Thanks @yanpozka

[gyuho]

Original fix and tests are at:
gyuho/goraph#50

And the fix for this repository here:
#9

Thanks again @yanpozka

[yanpozka]

Good job @gyuho !! You're welcome! Always it's a pleasure to find people who cares about algorithm.

[gyuho]

Thanks!