Piggybacking onto my previous post about graphs and DFS and BFS, you may have noticed there is also a weight assigned to each edge in a graph. This is because I will talk about path-finding algorithms, starting with Dijsktra’s Algorithm. There are plenty of resources online, such as Wikipedia’s Description that do a fairly good job of describing the algorithm.

However, none of them explain the algorithm in a real world scenario, so I decided to describe it using a city whose beauty was distracting to my path orientation, causing me to constantly get lost: Prague, Czech Republic.

A section of Prague with a graph overlay

If you were planning a trip in a few blocks of that intersection, and all you had was this map, how would you get from, for example, point P to point W? Intuitively, you would look at A and all edges connected to it (without using an illustrated map, i.e. from a table), pick the lowest one and repeat.

Here is a PDF of Dijsktra’s Algorithm in Action and an animated GIF.

Dijsktra Animation

And finally, the updated code in PHP.