Class BellmanFordWithParentCheckingHeuristic<TWeight>

Namespace

AlgorithmsSW.EdgeWeightedDigraph

Assembly

AlgorithmsSW.dll

A Bellman-Ford shortest path algorithm with a heuristic that skips relaxing a vertex if its parent is on the queue.

[ExerciseReference(4, 4, 32)]
public class BellmanFordWithParentCheckingHeuristic<TWeight> where TWeight : INumber<TWeight>, IMinMaxValue<TWeight>

Type Parameters

TWeight

The type of the edge weights.

Inheritance

object

BellmanFordWithParentCheckingHeuristic<TWeight>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

Applications.ApplyInterpolationRule<T, TBuffer>(TBuffer, Func<T, T, T>)

Applications.ApplyInterpolationRule<T, TBuffer>(TBuffer, Func<T, T, T>, int)

Applications.Interpolate<T, TBuffer>(TBuffer, Func<T, T, T>, int)

Applications.Substitute<T, TBuffer>(TBuffer, (T input, T[] output)[])

Comparable.ToComparable<T>(T, IComparer<T>)

Formatter.AsText<T>(T?)

Formatter.Describe<TLabel, TDescription>(TLabel, TDescription, string)

Formatter.Log<T>(T)

Formatter.Pretty<T>(T, params int[])

Remarks

I am not sure this is an improvement over the vanilla BellmanFord<TWeight>. In a graph with around 1_000 to 4_000 vertices, with 95% of edges (compared to a complete graph), the relaxing of a vertex is skipped on the order of 10 times.

 In benchmarks, this algorithm is not measurably faster.

 I do wonder if my implementation is correct.

Constructors

BellmanFordWithParentCheckingHeuristic(IReadOnlyEdgeWeightedDigraph<TWeight>, int)

public BellmanFordWithParentCheckingHeuristic(IReadOnlyEdgeWeightedDigraph<TWeight> graph, int sourceVertex)

Parameters

graph IReadOnlyEdgeWeightedDigraph<TWeight>

sourceVertex int

Methods

GetDistanceTo(int)

public TWeight GetDistanceTo(int vertex)

Parameters

vertex int

Returns

TWeight

GetEdgesOfPathTo(int)

public IEnumerable<DirectedEdge<TWeight>> GetEdgesOfPathTo(int target)

Parameters

target int

Returns

IEnumerable<DirectedEdge<TWeight>>

HasPathTo(int)

public bool HasPathTo(int vertex)

Parameters

vertex int

Returns

bool

NegativeCycle()

public IEnumerable<DirectedEdge<TWeight>> NegativeCycle()

Returns

IEnumerable<DirectedEdge<TWeight>>