4 ms·

Dijkstra's Algorithm

119 points by hn-user 10y ago

e19293001 10y ago
For those who want to learn about Dijkstra's Algorithm: I would prefer reading the original paper[0] written by Dijsktra himself. The explanation is so clear that I wish all algorithms were written and taught like this. The data structure and the steps are explained simply in plain english rather than a pseudo-code. Really. He's a very good writer. I'm not his student but by reading about him, the most important part in software/hardware development that I learned from him (especially on a large team) is to write a documentation/specification first before writing the code[1]. Their mode of interaction remains a model of disciplined engineering: They would first decide upon the interface between the hardware and the software, by writing a programming manual. Then the hardware designers would have to be faithful to their part of the contract, while Dijkstra, the programmer, would write software for the nonexistent machine. Two of the lessons he learned from this experience were the importance of clear documentation, and that program debugging can be largely avoided through careful design. [0] - http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.... [1] - https://web.archive.org/web/20031210213835/http://www.utexas.edu/faculty/council/2002-2003/memorials/Dijkstra/dijkstra.html https://web.archive.org/web/20031210213835/http://www.utexas...
- Silhouette 10y ago
  This sort of algorithm is also a demonstration of how useful different types of presentation can be when learning. The original paper isn't a bad source, but it's very wordy because words are all it uses. There's an animated diagram on the Wikipedia page for Dijkstra's algorithm[1] that probably is worth a thousand words, and given a brief introduction to the idea so you know what the diagram is illustrating, together with the pseudocode for the full algorithm shown later on that page, I reckon someone who understands the problem but didn't previously know this solution could understand the solution and write their own implementation in a few minutes. [1] https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
  - garaetjjte 10y ago
    Best introduction to Dijkstra algorithm and A*, with great visualisations is http://www.redblobgames.com/pathfinding/a-star/introduction.html http://www.redblobgames.com/pathfinding/a-star/introduction....
    - Silhouette 10y ago
      Yes, that is very nicely presented.
    - Jach 10y ago
      I was going to challenge you, since I thought that was going to be the older http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html http://theory.stanford.edu/~amitp/GameProgramming/AStarCompa... reference which I never found very helpful. The best intro I had to these was in a Game AI course and we basically implemented all these visualizations and more (bad screenshot: http://www.thejach.com/imgs/visibility_with_astar.png http://www.thejach.com/imgs/visibility_with_astar.png) to fully understand it. But the newer reference you linked is great and I'd agree it's the best public introduction.
  - Someone 10y ago
    "There's an animated diagram on the Wikipedia page for Dijkstra's algorithm" Dijkstra must be turning in his grave. He was strongly opposed to the use of pictures in his papers. I can't find a direct quote, but https://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1012.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/E... says: "But this historical explanation is no excuse for the fact that today Euclidean geometry, with all its known defects, is still taught as the prototype of a strictly deductive system. It is not. Its reliance on pictures is quoted as evidence for the value of “geometric intuition”, while in fact it is only a symptom of the defects of Euclid's axiomatization. (In passing I would like to add that I see more and more evidence that it is precisely the informality of the pictorial argument that defies the development of heuristics by means of which such arguments can be designed in an orderly fashion. This is in sharp contrast with the highly effective heuristics that could be developed for strictly formal environments.)"
douche 10y ago
Finally, this made it onto the front page... I like seeing an example of the TDD process with a more real algorithm than you usually see. Bowling score counters and reverse-polish calculators get a little tedious. I've been meaning to go through this series in depth http://www.daedtech.com/tag/chesstdd/ http://www.daedtech.com/tag/chesstdd/ It's hard to cultivate the proper mindset when you're constantly in get-shit-done-now-now-now mode all the time...
gefh 10y ago
This seems a little bit like 1) Draw two circles. 2) Draw the rest of the owl. I don't see that TDD is helping 'form' the algorithm at all. The format of the input and output, sure, but the core intellectual leap seems glossed over.
blt 10y ago
I can't understand how someone calls himself a "clean coder" but implements a graph algorithm entirely with strings. That is messy.
akssri 10y ago
Implementation in Lisp, https://github.com/matlisp/matlisp/blob/master/src/graph/graph.lisp#L261 https://github.com/matlisp/matlisp/blob/master/src/graph/gra...
justopinions 10y ago
PathFinder is poorly designed imo. What is the result of calling getPath or getMinLength before calling findPath? The correct way of returning the path calculation is Path findPath(); not void findPath() which stores the results as fields on PathFinder.
elcct 10y ago
Is it only me who finds this website unreadable?
- touristtam 10y ago
  No, I find the UX dreadful coming from a website that title itself "clean code". The style is bare and the author still manages poor presentation. At the very least a different style for the code would have been nice.
Scea91 10y ago
It's easy to come up with tests if you already know the solution. Nonetheless, this religious approach to TDD is a waste of time.
deleted 10y ago
[deleted]
yzh 10y ago
For those who are searching for improved Dijkstra's algorithm, delta-stepping is a good one: https://www.cs.utexas.edu/~pingali/CS395T/2012sp/papers/delta-stepping.pdf https://www.cs.utexas.edu/~pingali/CS395T/2012sp/papers/delt...
- cgearhart 10y ago
  Cool! Another (more modest) improvement is Uniform Cost Search[1] (see comparison with DA: https://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4017/4357 https://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFil... ) which then leads naturally to A* and bidirectional search which can be augmented with pre-processing. (Good summary: https://www.microsoft.com/en-us/research/publication/point-to-point-shortest-path-algorithms-with-preprocessing/ https://www.microsoft.com/en-us/research/publication/point-t... ) [1] Despite what wikipedia says, UCS is not the same as DA.

119 points by hn-user 10y ago

e19293001 10y ago

For those who want to learn about Dijkstra's Algorithm: I would prefer reading the original paper[0] written by Dijsktra himself. The explanation is so clear that I wish all algorithms were written and taught like this. The data structure and the steps are explained simply in plain english rather than a pseudo-code. Really. He's a very good writer. I'm not his student but by reading about him, the most important part in software/hardware development that I learned from him (especially on a large team) is to write a documentation/specification first before writing the code[1]. Their mode of interaction remains a model of disciplined engineering: They would first decide upon the interface between the hardware and the software, by writing a programming manual. Then the hardware designers would have to be faithful to their part of the contract, while Dijkstra, the programmer, would write software for the nonexistent machine. Two of the lessons he learned from this experience were the importance of clear documentation, and that program debugging can be largely avoided through careful design. [0] - http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.... [1] - https://web.archive.org/web/20031210213835/http://www.utexas.edu/faculty/council/2002-2003/memorials/Dijkstra/dijkstra.html https://web.archive.org/web/20031210213835/http://www.utexas...

Silhouette 10y ago
This sort of algorithm is also a demonstration of how useful different types of presentation can be when learning. The original paper isn't a bad source, but it's very wordy because words are all it uses. There's an animated diagram on the Wikipedia page for Dijkstra's algorithm[1] that probably is worth a thousand words, and given a brief introduction to the idea so you know what the diagram is illustrating, together with the pseudocode for the full algorithm shown later on that page, I reckon someone who understands the problem but didn't previously know this solution could understand the solution and write their own implementation in a few minutes. [1] https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- garaetjjte 10y ago
  Best introduction to Dijkstra algorithm and A*, with great visualisations is http://www.redblobgames.com/pathfinding/a-star/introduction.html http://www.redblobgames.com/pathfinding/a-star/introduction....
  - Silhouette 10y ago
    Yes, that is very nicely presented.
  - Jach 10y ago
    I was going to challenge you, since I thought that was going to be the older http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html http://theory.stanford.edu/~amitp/GameProgramming/AStarCompa... reference which I never found very helpful. The best intro I had to these was in a Game AI course and we basically implemented all these visualizations and more (bad screenshot: http://www.thejach.com/imgs/visibility_with_astar.png http://www.thejach.com/imgs/visibility_with_astar.png) to fully understand it. But the newer reference you linked is great and I'd agree it's the best public introduction.
- Someone 10y ago
  "There's an animated diagram on the Wikipedia page for Dijkstra's algorithm" Dijkstra must be turning in his grave. He was strongly opposed to the use of pictures in his papers. I can't find a direct quote, but https://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1012.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/E... says: "But this historical explanation is no excuse for the fact that today Euclidean geometry, with all its known defects, is still taught as the prototype of a strictly deductive system. It is not. Its reliance on pictures is quoted as evidence for the value of “geometric intuition”, while in fact it is only a symptom of the defects of Euclid's axiomatization. (In passing I would like to add that I see more and more evidence that it is precisely the informality of the pictorial argument that defies the development of heuristics by means of which such arguments can be designed in an orderly fashion. This is in sharp contrast with the highly effective heuristics that could be developed for strictly formal environments.)"

douche 10y ago

Finally, this made it onto the front page... I like seeing an example of the TDD process with a more real algorithm than you usually see. Bowling score counters and reverse-polish calculators get a little tedious. I've been meaning to go through this series in depth http://www.daedtech.com/tag/chesstdd/ http://www.daedtech.com/tag/chesstdd/ It's hard to cultivate the proper mindset when you're constantly in get-shit-done-now-now-now mode all the time...

gefh 10y ago

This seems a little bit like 1) Draw two circles. 2) Draw the rest of the owl. I don't see that TDD is helping 'form' the algorithm at all. The format of the input and output, sure, but the core intellectual leap seems glossed over.

blt 10y ago

I can't understand how someone calls himself a "clean coder" but implements a graph algorithm entirely with strings. That is messy.

akssri 10y ago

Implementation in Lisp, https://github.com/matlisp/matlisp/blob/master/src/graph/graph.lisp#L261 https://github.com/matlisp/matlisp/blob/master/src/graph/gra...

justopinions 10y ago

PathFinder is poorly designed imo. What is the result of calling getPath or getMinLength before calling findPath? The correct way of returning the path calculation is Path findPath(); not void findPath() which stores the results as fields on PathFinder.

elcct 10y ago

Is it only me who finds this website unreadable?

touristtam 10y ago
No, I find the UX dreadful coming from a website that title itself "clean code". The style is bare and the author still manages poor presentation. At the very least a different style for the code would have been nice.

Scea91 10y ago

It's easy to come up with tests if you already know the solution. Nonetheless, this religious approach to TDD is a waste of time.

deleted 10y ago

[deleted]

yzh 10y ago

For those who are searching for improved Dijkstra's algorithm, delta-stepping is a good one: https://www.cs.utexas.edu/~pingali/CS395T/2012sp/papers/delta-stepping.pdf https://www.cs.utexas.edu/~pingali/CS395T/2012sp/papers/delt...

cgearhart 10y ago
Cool! Another (more modest) improvement is Uniform Cost Search[1] (see comparison with DA: https://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4017/4357 https://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFil... ) which then leads naturally to A* and bidirectional search which can be augmented with pre-processing. (Good summary: https://www.microsoft.com/en-us/research/publication/point-to-point-shortest-path-algorithms-with-preprocessing/ https://www.microsoft.com/en-us/research/publication/point-t... ) [1] Despite what wikipedia says, UCS is not the same as DA.