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​(DirectedGraph graph, boolean shortestPath, FHeuristic fHeuristic)
    FloydWarshall Constructor

  • Method Summary

    Modifier and Type Method Description
    FHeuristic fHeuristic()
    Retrieve the F Heuristic
    DirectedGraph 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​(DirectedGraph 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 DirectedGraph 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