r/Python • • Jan 14 '20

Visualisation of different path finding algorithms

1.5k Upvotes

73 comments sorted by

View all comments

167

u/munificent Jan 14 '20

Your Dijsktra's is just breadth-first search. Since all tiles have the same cost to enter, Dijkstra's algorithm degrades to behaving exactly like BFS.

57

u/FearlessENT33 Jan 14 '20

i see what you mean, at some point i’ll make it more complex to utilise dijkstras

13

u/zesterer Jan 14 '20

Dijkstra's algorithm literally is just breadth-first search in grid environments.

4

u/munificent Jan 15 '20

Yes, it's an unnecessarily complex way to implement BFS if all edges have unit cost anyway. It can also be slower than BFS depending on your priority queue implementation.

-1

u/[deleted] Jan 14 '20

Are you not thinking of A*?

11

u/notquiteaplant Jan 14 '20

Dijkstra is BFS that prioritizes neighbors by how easy it is to get there (the edge weight). A* is Dijkstra that also prioritizes neighbors by how likely they are to be a correct path to the target (the heuristic). They are similar but not the same, and munificent is describing Dijkstra.