Floyd’s Algorithm

Floyd’s Algorithm works by first creating a two-dimensional array that stores information about the presence or absence of a link between each node and every other node. In short, it is a map of the subnet in array form. Once this is done, it tries to compute the shortest path between the source and destination node (which are chosen by the user). The metric used here is the number of hops. The algorithm tries to find a route with the minimum number of hops between the source and destination.

The figure below is the Floyd’s array for the example subnet shown earlier. A ‘1’ indicates the presence of a link, while a ‘0’ indicates its absence.

Subnet array

Figure 3: Subnet array

The algorithm starts off by parsing the array to check if a direct link is available between the source and destination nodes. If so, this is the “shortest path”. If not, then it checks if a valid route can be obtained by placing any one intermediate node. The first valid route is returned to the user. If no route is found, then it checks again with all combinations of two intermediate nodes. If still no valid route exists, three intermediate nodes are used.

Floyd's algorithm

Figure 4: Floyd’s algorithm

And similarly, more and more intermediate routes are added until a valid route between the source and destination is found, which is then displayed to the user. Since the algorithm starts off with the minimum number of intermediate nodes and then adds more, obviously the first valid computed route will be the shortest, and there is no further need to compute any alternative routes.

Please note that all combinations of nodes (other than the source and destination) are tried out for each number of intermediate nodes. For instance, if the algorithm is computing a route with two intermediate nodes, it tries every combination of available nodes, viz. 1-2,1-3,1-4…,2-3,2-4…, and so on.



The next page describes the algorithm of our program, which is a slightly “enhanced” version of the original Floyd’s algorithm described above, using a flowchart.