Package org.drip.graph.bellmanford

Class YenReducedRelaxationPathGenerator

java.lang.Object

org.drip.graph.shortestpath.OptimalPathGenerator

org.drip.graph.bellmanford.EdgeRelaxationPathGenerator

org.drip.graph.bellmanford.YenReducedRelaxationPathGenerator

public class YenReducedRelaxationPathGenerator
extends EdgeRelaxationPathGenerator

YenReducedRelaxationPathGenerator generates the Shortest Path for a Directed Graph using the Bellman-Ford Algorithm with a Yen (1970) Vertex Relaxation Trimming Scheme applied. The References are:

• Bang-Jensen, J., and G. Gutin (2008): Digraphs: Theory, Algorithms, and Applications 2^nd Edition Springer
• Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3^rd Edition MIT Press
• Kleinberg, J., and E. Tardos (2022): Algorithm Design 2^nd Edition Pearson
• Sedgewick, R. and K. Wayne (2011): Algorithms 4^th Edition Addison Wesley
• Wikipedia (2020): Bellman-Ford Algorithm https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

• Module = Computational Core Module
• Library = Graph Algorithm Library
• Project = Graph Optimization and Tree Construction Algorithms
• Package = Bellman Ford Shortest Path Family

Author:

Lakshmi Krishnamurthy

Constructor Summary

Constructors

Constructor	Description
YenReducedRelaxationPathGenerator(Directed<?> graph, boolean shortestPath, FHeuristic fHeuristic)	YenReducedRelaxationPathGenerator Constructor

Method Summary

Methods inherited from class org.drip.graph.bellmanford.EdgeRelaxationPathGenerator

augmentVertexes

Methods inherited from class org.drip.graph.shortestpath.OptimalPathGenerator

fHeuristic, graph, shortestPath, singlePair, singleSource

Methods inherited from class java.lang.Object

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

Constructor Details

YenReducedRelaxationPathGenerator

public YenReducedRelaxationPathGenerator(Directed<?> graph,
boolean shortestPath,
FHeuristic fHeuristic)
                                  throws java.lang.Exception

YenReducedRelaxationPathGenerator 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