Coding, Computer Science, Crafty, Geography, Murderous Maths, Notes on everyday life, Simon's sketch book

Pathfinding algorithms: Dijkstra’s and Breadth-first search

The photos below show Simon playing with Breadth-first search and Dijkstra’s algorithms to find the most efficient path from S to E on a set of graphs. The two more complex graphs are weighed and undirected. To make it more fun, I suggest we pretend we travel from, say, Stockholm to Eindhoven and name all the intermediate stops as well, depending on their first letters. And the weights become ticket prices. Just to make it clear, it was I who needed to add this fun bit with the pretend play, Simon was perfectly happy with the abstract graphs (although he did enjoy my company doing this and my cranking up a joke every now and then regarding taking a detour to Eindhoven via South Africa).

this was an example of how an algorithm can send you the wrong way if it has data of the “right” way being weighted more (due to traffic jams, for example)
Coding, Computer Science, Crafty, Geography, Geometry Joys, Murderous Maths, Simon's sketch book

Dijkstra’s pathfinding algorithm

“I have first built a maze, then I turned it into a graph and applied Dijkstra’s pathfinding algorithm!”

a maze to which Dijkstra’s pathfinding algorithm is applied

Simon learned this from the Computerphile channel. He later also attempted to solve the same maze using another pathfinding algorithm (A-Star).