4 ms·

Dijkstra's algorithm without a priority queue?

• jwilk 8y ago
  Where?
  • stochastic_monk 8y ago
    https://github.com/TheAlgorithms/Python/blob/master/Graphs/basic-graphs.py#L113-L131 https://github.com/TheAlgorithms/Python/blob/master/Graphs/b...
    • lorenzhs 8y ago
      This is terrible. The charitable interpretation would be that Dijkstra's original paper in 1959 didn't use a priority queue, either. But given the strange hard-coded distance maximum of 100000, that Prim's MST algorithm is implemented the same way, and that Kruskal is implemented without a Union Find datastructure, I'm going to have to say it again: this is terrible. Don't use this for learning.
      • stochastic_monk 8y ago
        I'd instead recommend Boost's Graph Library. It's not an easy piece of code to understand, but they have everything from Flord-Warshall and Kruskal's to Min-Cut and Dijkstra's in very generic implementations.