Package org.drip.graph.shortestpath

Class DijkstraPathGenerator

java.lang.Object

org.drip.graph.shortestpath.OptimalPathGenerator

org.drip.graph.shortestpath.DijkstraPathGenerator

public class DijkstraPathGenerator
extends OptimalPathGenerator

DijkstraPathGenerator generates the Shortest Path for a Directed Graph using the Dijkstra Algorithm. The References are:

• Dijkstra, E. W. (1959): A Note on Two Problems in Connection with Graphs Numerische Mathematik 1 269-271
• Felner, A. (2011): Position Paper: Dijkstra’s Algorithm versus Uniform Cost Search or a Case against Dijkstra’s Algorithm Proceedings of the 4^th International Symposium on Combinatorial Search 47-51
• Mehlhorn, K. W., and P. Sanders (2008): Algorithms and Data Structures: The Basic Toolbox Springer
• Russell, S., and P. Norvig (2009): Artificial Intelligence: A Modern Approach 3^rd Edition Prentice Hall
• Wikipedia (2019): Dijkstra's Algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

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

Author:

Lakshmi Krishnamurthy

Constructor Summary

Constructors

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

DijkstraPathGenerator

public DijkstraPathGenerator(DirectedGraph graph,
boolean shortestPath,
FHeuristic fHeuristic)
                      throws java.lang.Exception

DijkstraPathGenerator 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