Understanding Dijkstra's Algorithm
aos.github.io
Understanding Dijkstra's Algorithm
1–10 of 11 posts
Re: Understanding Dijkstra's Algorithm
#2I can highly reccomend the book “mazes for programmers” which introduces a lot of graph related alorithms in a clear, accessible way.
Dijkstra’s algorithm is on page 36 and explained in 8 paragrpahs.
Re: Understanding Dijkstra's Algorithm
#3The computerphile episode on this makes it quite clear as well.
https://www.youtube.com/watch?v=GazC3A4OQTE
Re: Understanding Dijkstra's Algorithm
#4I can highly reccomend the book “mazes for programmers” which introduces a lot of graph related alorithms in a clear, accessible way. Dijkstra’s algorithm is on page 36 and explained in 8 paragrpahs. https://media.pragprog.com/titles/jbmaze/first.pdf
Yeah, it’s a good book with great visuals. The author, Jamis Buck, actually lives in my town. He visited my University and gave a lecture on generating a Zelda like over-world by using maze algorithms. It was an interesting application. Jamis writes in Ruby and helped with Ruby on Rails. He has a good blog too [1].
Re: Understanding Dijkstra's Algorithm
#5I find Floyd–Warshall algorithm much more facinating. It took me almost 25 years to realize that it was different from the algorithm that I had deviced myself for solving the problem.
Dijkstra's algorithm seems rather obvious to me, as I discovered it myself after I head the problem description. A note in my diary seems to imply that I implemented it in LISP.
Re: Understanding Dijkstra's Algorithm
#6"At its heart, Dijkstra’s algorithm is really only a modified bread-first search."
First finish your bread, and only then attempt the search.
Re: Understanding Dijkstra's Algorithm
#7I felt similar to the first paragraph, that Dijkstra's algorithm was elevated in so.e way.
Then I found out that Dijkstra's algorithm is 'just' A* where the heuristic function is zero. :| Which is both incredibly simple and intuitive.
Re: Understanding Dijkstra's Algorithm
#8This is a pretty good explanation. Putting nodes in a priority queue at each stage is the trick here. I wish I had this explained in such a simple manner earlier.
Re: Understanding Dijkstra's Algorithm
#9I find Floyd–Warshall algorithm much more facinating. It took me almost 25 years to realize that it was different from the algorithm that I had deviced myself for solving the problem. Dijkstra's algorithm seems rather obvious to me, as I discovered it myself after I head the problem description. A note in my diary seems to imply that I implemented it in LISP.
Wow
Re: Understanding Dijkstra's Algorithm
#10I can highly reccomend the book “mazes for programmers” which introduces a lot of graph related alorithms in a clear, accessible way. Dijkstra’s algorithm is on page 36 and explained in 8 paragrpahs. https://media.pragprog.com/titles/jbmaze/first.pdf
bad taste, you give a link to 10 page version and tell people to look at p. 36