Package org.drip.graph.shortestpath

Class FloydWarshall

java.lang.Object
org.drip.graph.shortestpath.FloydWarshall
public class FloydWarshall
extends java.lang.Object
FloydWarshall generates the Shortest Path for a Directed Graph using the Floyd-Warshall Dynamic Programming Algorithm. The References are:

  • Chan, T. M. (2010): More Algorithms for All-Pairs Shortest Paths in Weighted Graphs SIAM Journal on Computing 39 (5) 2075-2089
  • Floyd, R. W. (1962): Algorithm 97: Shortest Path Communications of the ACM 5 (6) 345
  • Hougardy, S. (2010): The Floyd-Warshall Algorithm on Graphs with Negative Cycles Information Processing Letters 110 (8-9) 279-291
  • Warshall, S. (1962): A Theorem on Boolean Matrices Journal of the ACM 9 (1) 11-12
  • Wikipedia (2020): Floyd-Warshall Algorithm https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    FloydWarshall​(Directed<?> graph, boolean shortestPath, FHeuristic fHeuristic)
    FloydWarshall Constructor

  • Method Summary

    Modifier and Type Method Description
    FHeuristic fHeuristic()
    Retrieve the F Heuristic
    Directed<?> graph()
    Retrieve the Graph underlying the Path Generator
    boolean shortestPath()
    Indicate if the Shortest Path is Sought

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • FloydWarshall

      public FloydWarshall​(Directed<?> graph, boolean shortestPath, FHeuristic fHeuristic) throws java.lang.Exception
      FloydWarshall Constructor
      Parameters:
      graph - Graph underlying the Path Generator
      shortestPath - TRUE - Shortest Path Sought
      fHeuristic - F Heuristic
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • graph

      public Directed<?> graph()
      Retrieve the Graph underlying the Path Generator
      Returns:
      Graph underlying the Path Generator

    • shortestPath

      public boolean shortestPath()
      Indicate if the Shortest Path is Sought
      Returns:
      TRUE - Shortest Path Sought

    • fHeuristic

      public FHeuristic fHeuristic()
      Retrieve the F Heuristic
      Returns:
      The F Heuristic