Dijkstra's Algorithm | Hacker News Reader

Dijkstra's Algorithm

blog.cleancoder.com

119 pointshn-user18 comments

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....

[1] - https://web.archive.org/web/20031210213835/http://www.utexas...

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

Best introduction to Dijkstra algorithm and A*, with great visualisations is http://www.redblobgames.com/pathfinding/a-star/introduction....

Yes, that is very nicely presented.

I was going to challenge you, since I thought that was going to be the older 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) to fully understand it. But the newer reference you linked is great and I'd agree it's the best public introduction.

"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/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.)"

Well, I'm sorry if Dijkstra would have been offended, but vast amounts of human experience with teaching and presentation methods say pictures work, animations work, and interaction works. Awful presentation is unfortunately the accepted norm within academia, at least in scientific and mathematical disciplines, but that doesn't mean everyone else has to sink to the same depths when trying to pass on useful information or convey understanding.

https://www.cs.utexas.edu/~EWD/ewd12xx/EWD1255.PDF

At least one instance of using pictures to illustrate things.

Your quote is about being opposed to weak (informal, hard to show correctness or make consistent across the range of things he wanted to prove) proofs by diagramming, where he wanted more formal reasoning.

The man was no fool, in at least some of his presentations I've seen (videos) he also used diagrams and pictures to illustrate things. They're necessary on occasion.

EDIT: Typos from trying to comment from my phone.

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.

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

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.

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/delt...

Cool!

Another (more modest) improvement is Uniform Cost Search[1] (see comparison with DA: 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-t... )

[1] Despite what wikipedia says, UCS is not the same as DA.

Implementation in Lisp,

https://github.com/matlisp/matlisp/blob/master/src/graph/gra...

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.

Is it only me who finds this website unreadable?

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.

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/

It's hard to cultivate the proper mindset when you're constantly in get-shit-done-now-now-now mode all the time...

Reply on news.ycombinator.com