Before Finding the Fastest Route, Count the Questions
The delivery person must go from the warehouse to one customer on the shortest route. Nevertheless, prior to receiving an initial order, the dispatch center can find out the travel times between all warehouses, pickup locations, and delivery areas.
Both involve shortest paths; however, they are two different computing problems. One is the travel route to one customer. The other requires the construction of an entire table of travel routes.
For this reason, a technique invented more than 60 years ago remains a part of any computer science curriculum and software library. Floyd's algorithm is not a general solution to routing; it is a response to a particular type of problem posed.
Building a complete route table
A network consists of several points with links assigned weights. Points can be railway stations, computer servers, offices, or various stages in the process of manufacture. Link weights are distances, times, costs, or anything measurable.
The Floyd-Warshall algorithm, also called Floyd's algorithm, is an algorithm that calculates the shortest path between all pairs of points in a network. Instead of starting each route calculation from scratch, it repeatedly checks whether the path can be improved by passing through an intermediate point.
For example, the cost of shipment from A to C is ₹800. The cost of traveling directly from A to B is ₹300, and from B to C is ₹250. It updates the direct travel cost to ₹550. This calculation is repeated throughout the network until it cannot improve the calculation with any intermediary.
The outcome will be a table capable of answering any origin/destination query that may come up, making Floyd's algorithm especially useful when many route queries are expected.
Where advanced calculation becomes useful
It makes sense to calculate all routes for a small network that receives many routing requests.
A regional distributor may need to calculate the distance between every warehouse and every retail sector. A multiplayer map-based game may need to calculate travel between all of these key locations. A company analyzing internal communications can use this information to measure the level of connection between every department.
Here, the focus is not on a single traveler choosing a destination. Instead, it involves calculating many possible routes using Floyd's algorithm.
According to the official documentation of NetworkX, the Floyd–Warshall algorithm suits cases of dense graphs where most connections can be considered to exist. It has time complexity (O(n^3)) and space complexity of (O(n^2)).
A simple method can still be the wrong method
Suppose there are 100 places in a network. In most real-world scenarios, the computation would still be relatively easy. Now imagine that there are hundreds of thousands of road intersections, and then calculating for every pair of roads will be a waste of resources.
Here lies the charm of Floyd's algorithm. It is short, and students can easily understand how the Floyd algorithm works without many special-case scenarios. Although explainability is a nice property, it does not make the algorithm suitable for the given dataset.
A sparse network allows searching beyond the already connected network nodes. NetworkX provides numerous algorithms to find the shortest path, and shortest_path() in SciPy is flexible enough to use algorithms such as the Floyd-Warshall algorithm and Dijkstra’s algorithm, based on the input and the operation required.
The more relevant question would be, "Which shortest path algorithm is better suited to the given problem?" The real question is, "What needs to be computed, and what is the structure of the network?" Floyd's algorithm is only one of several possible answers.
Negative values require interpretation
The value of a route need not mean distance in the physical sense. An edge in the financial or scheduling network could represent a profit, a discount, a time correction, or even have a negative value.
Unlike the common application of Dijkstra’s algorithm, the Floyd-Warshall algorithm will work with negative edges. However, it will not be able to calculate the shortest path in cases where there is a negative cycle in the network, where the total of the cycle elements continuously reduces the cost of the cycle being repeated. In this case, there would in fact be no ‘shortest’ answer at all. This limitation is highlighted by both NetworkX and SciPy.
This is certainly something to learn from. The algorithm does not make any assumptions regarding the meanings of the numbers. A negative edge can either represent a real-world scenario or simply a mistake in the data. It's up to the programmer to decide when Floyd's algorithm is appropriate for the data.
Start with the decision, not the formula
It is important to learn Floyd's algorithm because it shows how a complex problem can be solved through repeated comparison. However, the lasting lesson from this algorithm is about problem framing.
The team needs to understand whether a routing algorithm is required, or whether the team needs one route, or whether the team needs routes from one node to all other nodes, or whether the team needs routes between all pairs of nodes. The team needs to consider the density and the size of the network, the meaning of the weights within the network, and the recalculation frequency.
If the network in question is rather small, dense, and has a great amount of routing requests, then the familiar algorithm would be the best choice for the task. At the same time, it is crucial to understand that in the case of a large network that has loose connections, an alternative solution might help solve the problem with much less effort.
Routing problems start with destinations. However, the correct algorithm choice does not depend on the number of destinations to be compared, but rather depends on the number of destinations that can be compared. Understanding the strengths and limitations of Floyd's algorithm helps ensure that the chosen solution matches the problem rather than applying a familiar method by default.