Dijkstra is too slow

[marltu]

Current Dijkstra implementation is very slow.

I tried running it on graph which contains ~100 edges and it ran ~1s. Other implementations are 100x faster.

[clue]

Thanks for sharing your findings 👍

I agree that there's certainly room for improvement as performance wasn't our main concern when designing this library. Would you care to link to the other implementations? Could you even perhaps provide a gist with your benchmarking script and results? Thanks in advance :)

[marltu]

I reimplemented this one in PHP:

https://github.com/prakhar1989/Algorithms

Ran much faster.

[clemens-tolboom]

@marltu that code is not PHP ... do you want to share your PHP code for this project?

[marltu]

Since I implemented it during my work hours, I'm unable to share the code, but basically it is based on https://github.com/prakhar1989/Algorithms/blob/master/dp/dijkstra.py, using SplPriorityQueue.

Function is very trivial, so it would not be hard to rewrite it in PHP and create some metrics.

I'll try to do it on my free time some day.

[clue]

Since I implemented it during my work hours, I'm unable to share the code

What a pity. Perhaps you can ask your boss for permission? :) After all, you'll get some free support, contributions, and perhaps publicity for this. Besides, some of my work hours have also been to support this project, too :)

Function is very trivial, so it would not be hard to rewrite it in PHP and create some metrics.

I agree that it shouldn't be too much work, indeed. It's just that it isn't particularly high priority on my todo list. So for now I'll have to wait for anybody else to pick this up. I'll keep this ticket open as a reminder.

[clue]

It's been a while this received any attention...

Dijkstra is too slow

too slow is hard to fix. So unless we can quantify / measure this, I'm afraid there's not much we can do.

That being said PR #79 will apply a whole new structure to our SSSP algorithms (and thus Dijkstra) and will certainly ease using them in a more efficient manner.

In case anybody feels like it's still too slow: PRs are very much appreciated :)