edu.bsu.cs.algorithm
Class Floyd

java.lang.Object
  |
  +--edu.bsu.cs.algorithm.Algorithm
        |
        +--edu.bsu.cs.algorithm.Floyd

public class Floyd

extends Algorithm

An animated implementation of the Floyd-Warshall Shortest Path algorithm.

References:
Stephen Warshall. A theorem on Boolean matrices. Journal of the ACM, 9(1):11-12, January 1962. http://doi.acm.org/10.1145/321105.321107
Robert W. Floyd. Algorithm 97: shortest path. Communications of the ACM, 5(6):345, June 1962. http://doi.acm.org/10.1145/367766.368168

Since:

31 Mar 1998

Version:

31 May 2002

Author:

Yang

, Fred , Elizabeth VandenBerg

Constructor Summary

Floyd()
Constructs a Floyd algorithm with a default name, type, and description.

Method Summary

double[][]	allDistances(JavaGraph jGraph)
int[][]	allTs(JavaGraph jGraph)
void	callOwnConstructor(JavaGraph jGraph, Vector inputs, Vector animation) Constructs a Floyd algorithm as in Floyd(JavaGraph, Vector, Vector).
double	distanceBetweenVertices(double[][] D, int firstVertex, int secondVertex)

Methods inherited from class edu.bsu.cs.algorithm.Algorithm

getCode, getDescription, getName, getType, setCode, setDescription, setFromResources, setName, setType, succeeded, succeeded

Methods inherited from class java.lang.Object

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

Constructor Detail

Floyd

public Floyd()

Constructs a Floyd algorithm with a default name, type, and description.

Defaults are as follows:
name = "Floyd-Warshall Shortest Path"
type = JeditPanel.TWOCLICKALGORITHM
description = "Finds the shortest path between two vertices based on the weights of the edges or arcs. Click on two vertices to start the algorithm."

Method Detail

callOwnConstructor

public void callOwnConstructor(JavaGraph jGraph,
                               Vector inputs,
                               Vector animation)

Constructs a Floyd algorithm as in Floyd(JavaGraph, Vector, Vector).

Specified by:

callOwnConstructor in class Algorithm

Parameters:

jGraph - the edu.bsu.cs.graph.JavaGraph that the algorithm is performed on

inputs - a Vector of inputs that consists of

• An Integer, if the algorithm uses a single vertex as a starting point
• Two Integers if the algorithm uses two vertices as starting points
• A String if the algorithm starts off of typed input
• Nothing if the algorithm runs automatically on a graph

animation - a Vector that is filled with AnimObjects as the algorithm proceeds. It must be instantiated before this method is called.

allTs

public int[][] allTs(JavaGraph jGraph)

Parameters:

jGraph - The JavaGraph.

allDistances

public double[][] allDistances(JavaGraph jGraph)

Parameters:

jGraph - The JavaGraph.

distanceBetweenVertices

public double distanceBetweenVertices(double[][] D,
                                      int firstVertex,
                                      int secondVertex)

Parameters:

D - The double[][] array that is built by calling allDistances(JavaGraph).

firstVertex - The first vertex.

secondVertex - The second vertex.