by Summer Zhou ’23
Computer science, or coding, is a powerful tool that can be used to solve real world problems, and it often involves finding the minimum distance. The word “distance” implies that the minimum distance is a measured value between two points—however, it is not a measurement in a strictly geometric sense. The minimum distance doesn’t have to be strictly a property of a geographic problem, but can be transformed into other things like weight, scores, and a variety of numerical information. It also can be an alternative expression of boolean values.
This is a hard concept to explain, so let us illustrate it with a real-life example: we want to travel from point A to point B on the subway, and to do so, we may need to transfer at a number of stations. With a map of the subway lines, we want to write a program that finds the most efficient route between two stations. In this circumstance, we first need to determine if we need to transfer to a different train at a transit station. This information can be recorded as a boolean value (true or false), and can be represented numerically (1 if we need to transfer, and 0 otherwise). Therefore, if City Hall Station is on the same subway line as the Park Station, the “distance” between them would be zero. On the other hand, if City Hall Station and Shopping Mall Station are not on the same line (if we need to transit to a different train), the “distance” between them would be one. This first step simplified the question from “what is the minimum distance between two stations,” into “how many stations do I need to transfer at,” allowing us to approach the problem more conceptually.
This is one among thousands of real world examples where a problematic situation can be interpreted as the “distance” between two points. Because finding the minimum distance is an essential step to this method of problem solving, computer scientists presented a number of algorithms that calculate the minimum distance, and one of the most popular is Floyd-Warshall.
The essence of Floyd-Warshall is finding a “transition point” and replacing the original distance with the updated ones. take the graph below as an example. When the information is first put into our program, it is stored in a two-dimensional array. There are many other ways to store graphic information, but let us use a simple two-dimensional array (or a list depending on the programming language). At first, the minimum distance between any two points is the weight of the line connecting them (or null if there is no line in between). As we are running the code, the minimum distances will be updated. In the graph below, we can see that the weight of the line V1V3 is 7. However, starting from v1, if we visit v2 first before visiting v3, the distance would be five, which is better than 7. So how do we make sure that we update this information, and guarantee that the distances stored in the end can not be further updated by transitioning at some other points? The solution is to make every point on a graph a “transition point” exactly once. When we assign a point at a “transition point”, we examine if the minimum distance between two points will become smaller if they transfer from this point.
The code of Floyd-Warshall has only five lines. The C++ version of it is written below:
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][k]+dis[k][j]<dis[i][j]){
dis[i][j]=dis[i][k]+dis[k][j]; //update the distance if transitioning at k makes it smaller
}
}
}
}Compared to other famous algorithms for finding minimum distance like Dijkstra and Bellman-Ford, Floyd-Warshall is the most useful when finding the minimal distance between any two given points on the graph instead of the distance relating to one specific point.