Understanding Dijkstra's Algorithm(aos.github.io)

aos.github.io

https://aos.github.io/2018/02/24/understanding-dijkstras-algorithm/

10 comments

I 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

johnsonjo8 lat temu

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

[1]: http://weblog.jamisbuck.org

CraneWorm8 lat temu

bad taste, you give a link to 10 page version and tell people to look at p. 36

tomelders8 lat temu

Ah, ah ha. Hah. My bad.

superflyguy8 lat temu

"At its heart, Dijkstra’s algorithm is really only a modified bread-first search."

First finish your bread, and only then attempt the search.

gbtw8 lat temu

The computerphile episode on this makes it quite clear as well. https://www.youtube.com/watch?v=GazC3A4OQTE

fjfaase8 lat temu

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

1mike128 lat temu

Wow

eximius8 lat temu

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

abhishekjha8 lat temu

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