Class BellmanFordShortestPathAlgorithm<TVertex, TEdge>

Bellman Ford shortest path algorithm.

Inheritance
System.Object
AlgorithmBase<IVertexAndEdgeListGraph<TVertex, TEdge>>
RootedAlgorithmBase<TVertex, IVertexAndEdgeListGraph<TVertex, TEdge>>
ShortestPathAlgorithmBase<TVertex, TEdge, IVertexAndEdgeListGraph<TVertex, TEdge>>
BellmanFordShortestPathAlgorithm<TVertex, TEdge>
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: QuikGraph.Algorithms.ShortestPath
Assembly: QuikGraph.dll
Syntax
public sealed class BellmanFordShortestPathAlgorithm<TVertex, TEdge> : ShortestPathAlgorithmBase<TVertex, TEdge, IVertexAndEdgeListGraph<TVertex, TEdge>>, IAlgorithm<IVertexAndEdgeListGraph<TVertex, TEdge>>, IComputation, IAlgorithmComponent, IVertexColorizerAlgorithm<TVertex>, ITreeBuilderAlgorithm<TVertex, TEdge>, IDistancesCollection<TVertex> where TEdge : IEdge<TVertex>
Type Parameters
Name Description
TVertex

Vertex type.
TEdge

Edge type.
Remarks

The Bellman-Ford algorithm solves the single-source shortest paths problem for a graph with both positive and negative edge weights.

If you only need to solve the shortest paths problem for positive edge weights, Dijkstra's algorithm provides a more efficient alternative.

If all the edge weights are all equal to one then breadth-first search provides an even more efficient alternative.

Constructors

| Improve this Doc View Source

BellmanFordShortestPathAlgorithm(IAlgorithmComponent, IVertexAndEdgeListGraph<TVertex, TEdge>, Func<TEdge, Double>, IDistanceRelaxer)

Initializes a new instance of the BellmanFordShortestPathAlgorithm<TVertex, TEdge> class.

Declaration
public BellmanFordShortestPathAlgorithm(IAlgorithmComponent host, IVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph, Func<TEdge, double> edgeWeights, IDistanceRelaxer distanceRelaxer)
Parameters
Type Name Description
IAlgorithmComponent host

Host to use if set, otherwise use this reference.
IVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph

Graph to visit.
System.Func<TEdge, System.Double> edgeWeights

Function that computes the weight for a given edge.
IDistanceRelaxer distanceRelaxer

Distance relaxer.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
System.ArgumentNullException

edgeWeights is null.
System.ArgumentNullException

distanceRelaxer is null.
| Improve this Doc View Source

BellmanFordShortestPathAlgorithm(IVertexAndEdgeListGraph<TVertex, TEdge>, Func<TEdge, Double>)

Initializes a new instance of the BellmanFordShortestPathAlgorithm<TVertex, TEdge> class.

Declaration
public BellmanFordShortestPathAlgorithm(IVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph, Func<TEdge, double> edgeWeights)
Parameters
Type Name Description
IVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph

Graph to visit.
System.Func<TEdge, System.Double> edgeWeights

Function that computes the weight for a given edge.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
System.ArgumentNullException

edgeWeights is null.
| Improve this Doc View Source

BellmanFordShortestPathAlgorithm(IVertexAndEdgeListGraph<TVertex, TEdge>, Func<TEdge, Double>, IDistanceRelaxer)

Initializes a new instance of the BellmanFordShortestPathAlgorithm<TVertex, TEdge> class.

Declaration
public BellmanFordShortestPathAlgorithm(IVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph, Func<TEdge, double> edgeWeights, IDistanceRelaxer distanceRelaxer)
Parameters
Type Name Description
IVertexAndEdgeListGraph<TVertex, TEdge> visitedGraph

Graph to visit.
System.Func<TEdge, System.Double> edgeWeights

Function that computes the weight for a given edge.
IDistanceRelaxer distanceRelaxer

Distance relaxer.
Exceptions
Type Condition
System.ArgumentNullException

visitedGraph is null.
System.ArgumentNullException

edgeWeights is null.
System.ArgumentNullException

distanceRelaxer is null.

Properties

| Improve this Doc View Source

FoundNegativeCycle

Indicates if a negative cycle was found in the graph.

Declaration
public bool FoundNegativeCycle { get; }
Property Value
Type Description
System.Boolean

Methods

| Improve this Doc View Source

Clean()

Called on algorithm cleanup step.

Declaration
protected override void Clean()
Overrides
QuikGraph.Algorithms.AlgorithmBase<QuikGraph.IVertexAndEdgeListGraph<TVertex, TEdge>>.Clean()
| Improve this Doc View Source

Initialize()

Called on algorithm initialization step.

Declaration
protected override void Initialize()
Overrides
QuikGraph.Algorithms.ShortestPath.ShortestPathAlgorithmBase<TVertex, TEdge, QuikGraph.IVertexAndEdgeListGraph<TVertex, TEdge>>.Initialize()
| Improve this Doc View Source

InternalCompute()

Applies the Bellman Ford algorithm.

Declaration
protected override void InternalCompute()
Overrides
QuikGraph.Algorithms.AlgorithmBase<QuikGraph.IVertexAndEdgeListGraph<TVertex, TEdge>>.InternalCompute()
Remarks

Does not initialize the predecessor and distance map.

Events

| Improve this Doc View Source

EdgeMinimized

Fired during the second stage of the algorithm, during the test of whether each edge was minimized. If the edge is minimized then this event is raised.

Declaration
public event EdgeAction<TVertex, TEdge> EdgeMinimized
Event Type
Type Description
EdgeAction<TVertex, TEdge>
| Improve this Doc View Source

EdgeNotMinimized

Fired during the second stage of the algorithm, during the test of whether each edge was minimized. If the edge was not minimized, this event is raised. This happens when there is a negative cycle in the graph.

Declaration
public event EdgeAction<TVertex, TEdge> EdgeNotMinimized
Event Type
Type Description
EdgeAction<TVertex, TEdge>
| Improve this Doc View Source

EdgeNotRelaxed

Fired if the distance label for a target vertex is not decreased.

Declaration
public event EdgeAction<TVertex, TEdge> EdgeNotRelaxed
Event Type
Type Description
EdgeAction<TVertex, TEdge>
| Improve this Doc View Source

ExamineEdge

Fired on every edge in the graph (|V| times).

Declaration
public event EdgeAction<TVertex, TEdge> ExamineEdge
Event Type
Type Description
EdgeAction<TVertex, TEdge>
| Improve this Doc View Source

InitializeVertex

Fired on each vertex in the graph before the start of the algorithm.

Declaration
public event VertexAction<TVertex> InitializeVertex
Event Type
Type Description
VertexAction<TVertex>

Implements

Extension Methods