Package org.drip.graph.bellmanford

Class EdgeRelaxationPathGenerator

java.lang.Object

org.drip.graph.shortestpath.OptimalPathGenerator

org.drip.graph.bellmanford.EdgeRelaxationPathGenerator

Direct Known Subclasses:

EdgePartitionGenerator, YenReducedRelaxationPathGenerator

public class EdgeRelaxationPathGenerator
extends OptimalPathGenerator

EdgeRelaxationPathGenerator generates the Shortest Path for a Directed Graph using the Bellman-Ford Algorithm. 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
EdgeRelaxationPathGenerator(Directed<?> graph, boolean shortestPath, FHeuristic fHeuristic)	EdgeRelaxationPathGenerator Constructor

Method Summary

Modifier and Type	Method	Description
VertexAugmentor	augmentVertexes(java.lang.String sourceVertexName)	Generate the Augmented Vertex Suite starting from the Source Vertex

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

EdgeRelaxationPathGenerator

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

EdgeRelaxationPathGenerator 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

augmentVertexes

public VertexAugmentor augmentVertexes(java.lang.String sourceVertexName)

Description copied from class: OptimalPathGenerator

Generate the Augmented Vertex Suite starting from the Source Vertex

Specified by:

augmentVertexes in class OptimalPathGenerator

Parameters:

sourceVertexName - The Source Vertex Name

Returns:

The Augmented Vertex Suite