edu.rit.clu.network

Class FloydSeq

java.lang.Object

edu.rit.clu.network.FloydSeq

public class FloydSeq
extends java.lang.Object

Class FloydSeq is a sequential program that uses Floyd's Algorithm to calculate the length of the shortest path from each node to every other node in a network, given the distance from each node to its adjacent nodes.

Floyd's Algorithm's running time is O(N³), where N is the number of nodes. The algorithm is as follows. On input, D is an NxN matrix where D[i,j] is the distance from node i to adjacent node j; if node j is not adjacent to node i, then D[i,j] is infinity. On output, D[i,j] has been replaced by the length of the shortest path from node i to node j; if there is no path from node i to node j, then D[i,j] is infinity.

     for i = 0 to N-1
         for r = 0 to N-1
             for c = 0 to N-1
                 D[r,c] = min (D[r,c], D[r,i] + D[i,c])
 

Usage: java edu.rit.clu.network.FloydSeq infile outfile
infile = Input distance matrix file
outfile = Output distance matrix file

The input file (infile) is a binary file written in the format required by class DoubleMatrixFile.

The output file (outfile) is a binary file written in the format required by class DoubleMatrixFile containing the distance matrix after running Floyd's Algorithm.

The computation is performed sequentially in a single processor. The program measures the total running time (including I/O) and the computation's running time (excluding I/O). This establishes a benchmark for measuring the running time on a parallel processor.

Method Summary

Modifier and Type	Method and Description
static void	main(java.lang.String[] args) Main program.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

main

public static void main(java.lang.String[] args)
                 throws java.lang.Throwable

Main program.

Throws:

java.lang.Throwable