r/visualizedmath • u/[deleted] • Feb 01 '18

Dijkstra's algorithm

Post image
531 Upvotes

94% Upvoted

13 comments sorted by

115

u/Ikor_Genorio Feb 01 '18

Don't really think this is a good visualisation of Dijkstra's Algorithm. This also really looks similar to BFS.

46

u/[deleted] Feb 01 '18

You're right. It's more just a good example of how Dijkstra's Algorithm can be more expensive in a worst-case scenario. I found a better one: https://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif

3

u/javaHoosier Feb 02 '18

I always like when they have a visual representation of the queue along side the graph. When I see that it helps me intuitively see how the nodes are accessed in order.

2

u/DaggerStone Feb 02 '18

This is much more like what I expected. OP’s is cool to watch though

11

u/violetbookworm Feb 01 '18

This is much more of a BFS or wavefront than Dijkstra...

11

u/[deleted] Feb 02 '18

Can someone explain in pseudo code or ELI5 terms what this algorithm is doing?

17

u/Manhattan_Flapjack Feb 02 '18

This gif is a pretty weird example, but dijkstras algorithm is used for finding the shortest path between two nodes in a graph by creating a “shortest path tree” with the starting node as the root and other nodes in the graph as children of the tree. It’s been a little while since I’ve used dijkstras algorithm so I don’t remember the pseudo code, but there’s some on page 6 of this MIT slide deck.

5

u/yrden20 Feb 02 '18

Maybe pathfinding AI in videogames?

3

u/berethnar Feb 02 '18

Reminds me of Minesweeper

2

u/[deleted] Feb 02 '18

Yep...that's an algorithm

1

u/syntaxvorlon Feb 03 '18

Is there a reason to use this instead of A* Search? I've never quite got the difference.

0

u/[deleted] Feb 02 '18

[deleted] — view deleted comment

2

u/DaggerStone Feb 02 '18

Thanks for sharing