Class BellmanFordShortestDistanceTreeFinder

A IShortestDistanceFinder implementation based on the Bellman-Ford algorithm.

Inheritance
System.Object
BellmanFordShortestDistanceTreeFinder
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.Graphs.ShortestDistanceTree
Assembly: MoreStructures.dll
Syntax
public class BellmanFordShortestDistanceTreeFinder : IShortestDistanceTreeFinder
Remarks

REQUIREMENTS
- Same as BellmanFordShortestDistanceFinder.

ALGORITHM
- The algorithm closely resembles the one used in BellmanFordShortestDistanceFinder, with the only main difference that paths from the start vertex are reconstructed, since that would need to be done for each of the vertices of the graph, resulting in a worst case O(v^2) Space Complexity.
- Unlike DijkstraShortestDistanceTreeFinder, which can improve w.r.t. DijkstraShortestDistanceFinder on the average runtime, while the worst case is still bound to the total number of vertices in the graph, BellmanFordShortestDistanceTreeFinder cannot provide the same average running time improvement over BellmanFordShortestDistanceFinder, since the Bellman-Ford algorithm still requires v - 1 iterations to find optimal distances from the start vertex, and one iteration more, to be able to identify negative cycles and set shortest distance to minus infinity, for all vertices reachable from a negative cycle.

COMPLEXITY
- Same analysis as in BellmanFordShortestDistanceFinder.
- The fact that the algorithm doesn't reconstruct shortest paths doesn't reduce the overall complexity, which is bound to the v iterations of the main loop of the algorithm, each one relaxing at most e edges.
- Therefore, as in single path Bellman-Ford's algorithm variant, Time Complexity is O(v * (v * Tn + e)) and Space Complexity is O(v + Sn), where Tn and Sn are the time and space to retrieve the neighborhood of a single vertex.

Constructors

| Improve this Doc View Source

BellmanFordShortestDistanceTreeFinder(Func<IVisitStrategy>)

Declaration
public BellmanFordShortestDistanceTreeFinder(Func<IVisitStrategy> visitStrategyBuilder)
Parameters
Type Name Description
Func<IVisitStrategy> visitStrategyBuilder

Remarks

Properties

| Improve this Doc View Source

VisitStrategyBuilder

A building function able to instantiate the IVisitStrategy to be used to find all reachable vertices of vertices relaxed in the last iteration of the main loop of the Bellman-Ford algorithm, by running a Depth First Searches from the start vertex via DepthFirstSearchFromVertex(IGraph, Int32).

Declaration
public Func<IVisitStrategy> VisitStrategyBuilder { get; }
Property Value
Type Description
Func<IVisitStrategy>

Methods

| Improve this Doc View Source

FindTree(IGraph, IGraphDistances, Int32)

Declaration
public BestPreviouses FindTree(IGraph graph, IGraphDistances distances, int start)
Parameters
Type Name Description
IGraph graph
IGraphDistances distances
System.Int32 start
Returns
Type Description
BestPreviouses
Remarks

Implements

Extension Methods