Flowchart

Our algorithm makes an important addition to Floyd’s original algorithm. Along with the minimum number of hops, it also uses a link length metric to compute the shortest path. As per Floyd’s algorithm, it first tries to find a route with the minimum number of hops between the source and destination. However, it does not stop when the first valid route is found. It tries to find alternative routes with the same number of hops. If it finds such alternative routes, it then calculates the total physical length of all the routes separately and compares them. The shortest route is chosen.

The following is the flowchart for our version of Floyd’s algorithm:

Floyd's algorithm flowchart

Figure 5: Floyd’s algorithm flowchart

The user is first asked to enter specific data about each node individually, viz. the number of nodes it is connected to and the IDs of each of those nodes. Based on this information, a array of the subnet map is prepared. Using this array, the algorithm tries to find out the shortest path between the source and destination nodes (also entered by the user).



The algorithm first tries to check if a direct link is present. If not, it tries to come up with a valid route by adding successively more intermediate nodes (beginning with 1) and trying out all combinations of nodes for each number of nodes. The intermediate nodes are referred to as hops. Upon finding a valid route, it checks for alternative routes with the same number of hops. If any are found, the lengths of all routes are computed and the shortest route is delivered to the user.

For example, if the source and destination nodes are A and O respectively, the algorithm first checks for a direct link between them. It does this by checking the value of array_name[a,o]. Since this is zero (refer to the array table given on the previous page), it then checks for a valid route with one intermediate node. It starts off by keeping B as the intermediate node and checks if links are present between A and B and B and O. This is done by checking if both array_name[a,b] and array_name[b,o] are ‘1’. If true, the route is valid. However, it still checks for alternate routes using C, D, E,… N as the intermediate node. If any are found, total lengths for all valid routes are computed and compared and the shortest route is chosen (e.g. length of route A-B-O is array_name[a,b].length + array_name[b,o].length).

If no valid routes are found with one intermediate node, the entire process is repeated using two intermediate nodes. If still no valid routes exist, we check using three intermediate nodes. And so on until a valid route is found for any number of intermediate nodes.

The program finally displays the shortest path in a convenient, easy-to-read way.

Click here to download the program code (Turbo C++).