Computer Algorithms 2

Hello again! I would like to talk about algorithms more, since as I have expanded my knowledge they have become more and more interesting. These algorithms can be used in more ways than just for competitive programming (well of course, otherwise they wouldn’t have been made, but I’m beginning to get to where it touches my daily life), and one such example I will explore today is Dijkstra’s algorithm being used for pathfinding on maps and navigation.

Something most people will have done in today’s world is enter an address into their navigation app on their phone, and within seconds have a calculated route pop up to take them there. However, computers can’t just “eye-ball it” like humans can and just draw a line in that is in the general direction of the destination, it would not account for all edge cases where maybe there isn’t a direct path, or a path close to a direct path. There are actually algorithms that try to do this, but it doesn’t guarantee that it is the fastest path, but Dijkstra’s algorithm can.

Let’s go into how this works:

Let’s consider the map as nodes with undirected weighted edges connecting them, forming a graph. Let’s say that at every intersection or exit in every road we represent that as a node, and every piece of road connecting intersections is an edge, with a certain weight that is the amount of time it takes to get from one end of the edge to the other, and vice versa (This assumes that all roads allow for two-way travel, but you can also make directed edges instead, the algorithm works nonetheless).

After establishing this graph, you can make/pick a node closest to the user’s location as the starter node (there are different ways to do this, I won’t get into it) and make it apart of the graph. I won’t get into all of the details of what the algorithm does (tutorials for programmers exist and I just want to explain how this is used) but essentially we pick the node that takes the shortest time to get to and add that to a makeshift “visited” list that includes all of the nodes that have been added (at the beginning this list only includes the starter node). After adding this node, we add all of the nodes’ edges to a list of sorted edges coming from all nodes in the “visited” list. We keep picking the shortest edge and adding the node that is connected to the edge to the “visited” list. This continues until the destination node has been added, and in our estimates list the number for that node will no longer be an estimate- it will be the actual shortest time to get there!

There are different ways to prove that this will work, and the way I like to think about it is say that there are just 2 ways to get from point A to point B. Getting from point A to point B directly takes 5 units, while getting to point B via point C takes 7 units (we only see that getting from A to C takes 6 units, and then from C to B 1 unit). We know that the direct path is faster because if there was another “theoretically faster path” it would have to be through point C, and if we were to go through point C well we would have to spend 6 units first, and no matter what is after it it would take longer than the mere 5 units to go directly. Obviously this is not a formal proof, but it’s the best way to see how this works without knowing theory.

Conclusions:

Algorithms are cool! They work in different but fascinating ways, and can be applied to a lot of different topics. In my example with Dijkstra’s algorithm you can apply it to train, plane, and player routes in a variety of ways, and while of course there are other algorithms that can improve performance, they all show how with a bit of theory and practice you can solve just about any problem!