Hacker News new | past | comments | ask | show | jobs | submit login

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


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.


Yes, that is very nicely presented.


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




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: