The algorithm that the pupils have just explored in this module is the shortest path algorithm. The technical name of this algorithm is Breadth-First Search Algorithm or simply the BFS algorithm. Invented in 1945, it allows us to search a graph by first exploring a source node, then its successors, then the unexplored successors of the successors, etc. The Breadth-First Search algorithm is used to calculate the distances of all the nodes from the source node on a graph. The BFS works by using a queue in which it takes the first vertex and places its unexplored neighbours last. The already explored nodes are marked in order to avoid exploring the same node several times. This algorithm only works on unweighted graphs, i.e., graphs on which the nodes are connected by edges, all of which are unweighted. It is indeed the case for the graphs in this module: two nodes (here configurations) are connected by an edge if one can go from one configuration to another with a single crank handle movement. On the other hand, the BFS works for directed and undirected graphs. A directed graph is a graph in which the edges between two nodes are directed, i.e., they go from one node to another (Diestrel, 2018), or have a sense of direction. As the Involution© game is symmetrical (if one can go from configuration A to configuration B with a single movement, one can go from B to A with the reverse movement, which is indeed exactly the same movement), the graphs explored in this module are undirected. The Computer Science Department of Cornell University published a series of video introductions to the BFS which last 15 minutes in total (Gries, n. d.).

Some graphs can also be weighted. The road network graph we saw in this module is a weighted graph: the distance between the two junctions varies from one situation to another. The graph must take this into account by assigning a weight to the edges. The shortest path problem is therefore no longer necessarily the path that crosses the fewest nodes and the BFS does not work on weighted graphs. The Dijkstra’s algorithm is a well-known algorithm that gives the shortest path for weighted and unweighted graphs, both directed and undirected. It bears the name of its inventor, Edsger Dijkstra, and was published for the first time in 1959 (Dijkstra, 1959). The Dijkstra’s algorithm works as follows: the algorithm starts at a source node and calculates the distances between this node and all other nodes on the graph. It then chooses the closest node to the source node. This node is added into a queue along with the source node, then all the distances are re-evaluated: if the distance between the source node and another node is shorter by passing through the new node, then it is replaced by the shortest distance. The algorithm continues as such until it has crossed all the nodes, which enables minimum distances between the source node and all the other nodes to be established. The Computer Science Department of Cornell University has also published an introduction to the Dijkstra’s algorithm (Gries, n. d.).

On several occasions, the mathematician J. H. C. Whitehead stated that “combinatorics is the slums of topology” (Cameron, 2011). Combinatorics is a mathematical discipline which is part of graph theory. At the start of the 20^th century, this view of graph theory became widespread among other mathematicians, but it has significantly, or rather completely, changed today. Graph theory is an important tool for studying the links between complex systems. As soon as a system can be represented diagrammatically in the form of nodes and edges, graph theory can be applied. These systems can be very diverse: road networks, urban data network, etc. The applications in the computational world are now endless. Some very important examples (Flovik, 2020) are:

• The spread of the COVID-19 virus throughout communities
• The ranking of webpages in search engines (such as Google)
• Network security
• GPS navigators
• And many others

Let’s go back to GPS navigators (such as Google Maps, Waze, etc.), which are also involved in this module. GPS navigation systems are part of the graph theory applications which have a direct impact on our daily lives: we often rely on these systems to get to a place via the shortest (or quickest) route. A road network can be represented by a graph on which the nodes are junctions and buildings, and whose edges are the sections of the roads that connect them. As some roads are one-way, the graph is directed (unlike the Involution© graph which is undirected). The navigation system calculates an optimal route between two points of the network, based on the criteria defined by the user (it optimises either the length of the journey, the time of the journey or favours motorways, etc.). To illustrate the idea, imagine that the system is seeking to minimise the length of journeys. To model the problem, we must add information to the directed graph which models the road network. Each section of the road is assigned with a weight that represents exactly the length of that section. Therefore, navigators use directed and weighted graphs. The shortest path algorithm that navigators use is based on the Dijkstra’s algorithm (Teheux, 2019).

Interestingly, GPS navigation systems implement the Dijkstra’s algorithm in a reverse way. More precisely, if the goal of the user is to get from node A to node B, the navigation system applies the Dijkstra’s algorithm to the resulting graph by reversing the edges of the road network graph with node B as the source node. The outcome is thus the shortest path from B to A. However, you only have to reverse this path to get the desired path. The idea behind this inversion is an economy of calculations. It is not uncommon for us, as drivers, to leave the route recommended by the navigator (we take a wrong turn, a road is closed to traffic, we change our plan at the last minute, etc.). If the algorithm had already performed the search for the shortest path in the right direction, it should start again (as we find ourselves in a place that was unforeseen in the algorithm’s calculations) and all the calculations made before would have been lost. On the other hand, starting at the end, the algorithm has already calculated the shortest path from any point (within a reasonable radius) to the end point. Consequently, even if we change the itinerary, the algorithm is able to quickly provide us with an alternative (Teheux, 2019).

Although pure graph theory is an abstract and mathematical discipline, it shows that it has plenty of concrete and interesting applications in computer science. In any case, as world-renowned computer scientist Leslie Lamport states “If you really want to do things right, you need to write your algorithm in the terms of mathematics.” (Han, 2022).

References
Cameron, Peter J. (2011). Aftermath. Preprint. https://arxiv.org/pdf/1111.4050.pdf
Diestel, Reinhard. (2018). Graph theory (5th Ed.). Graduate Texts in Mathematics, 173. Berlin : Springer.
Dijkstra, Edsger W. (1959). A note on two problems in connexion with graphs. Numer. Math., 1, 269 – 271. https://doi.org/10.1007/BF01386390 
Flovik, Vegard. (2020). What is Graph Theory, and why should you care. From graph theory to path optimization. Towards Data Science. https://towardsdatascience.com/what-is-graph-theory-and-why-should-you-care-28d6a715a5c2
Gries, David. (n.d.). Depth-first search and breadth-first search. https://www.cs.cornell.edu/courses/JavaAndDS/dfs/dfs01.html
Gries, David. (n.d.). The shortest-path algorithm. https://www.cs.cornell.edu/courses/JavaAndDS/shortestPath/shortestPath.html
Han, Sheon. (2022). How to Write Software With Mathematical Perfection.Quantamagazine. https://www.quantamagazine.org/computing-expert-says-programmers-need-more-math-20220517
Teheux, Bruno. (2019). À la recherche des chemins les plus courts. Losange, N 46, 45-54.