Dijkstra's Algorithm
blog.cleancoder.com
Dijkstra's Algorithm
1–10 of 20 posts
Re: Dijkstra's Algorithm
#2For 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...
Re: Dijkstra's Algorithm
#3Finally, 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...
Re: Dijkstra's Algorithm
#4For 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…
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.
Re: Dijkstra's Algorithm
#5This 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.
Re: Dijkstra's Algorithm
#6I can't understand how someone calls himself a "clean coder" but implements a graph algorithm entirely with strings. That is messy.
Re: Dijkstra's Algorithm
#7Implementation in Lisp,
https://github.com/matlisp/matlisp/blob/master/src/graph/gra...
Re: Dijkstra's Algorithm
#8For 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…
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, togethe…
Best introduction to Dijkstra algorithm and A*, with great visualisations is http://www.redblobgames.com/pathfinding/a-star/introduction....
Re: Dijkstra's Algorithm
#9For 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…
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, togethe…
"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.)"
Re: Dijkstra's Algorithm
#10Is it only me who finds this website unreadable?