Class BellmanFordShortestPath<TVertex, TEdge, TWeight>

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

The Bellman-Ford shortest-path algorithm. Supports negative edge weights; throws NegativeCycleException when a negative cycle is reachable from the source. On undirected graphs each edge acts as two opposite arcs, so any negative undirected edge is itself a negative cycle.

public sealed class BellmanFordShortestPath<TVertex, TEdge, TWeight> : IShortestPathAlgorithm<TVertex, TEdge, TWeight> where TVertex : notnull where TEdge : IEdge<TVertex> where TWeight : INumber<TWeight>

Type Parameters

TVertex

The vertex type.

TEdge

The edge type.

TWeight

The numeric weight type.

Inheritance

object

BellmanFordShortestPath<TVertex, TEdge, TWeight>

Implements

IShortestPathAlgorithm<TVertex, TEdge, TWeight>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Constructors

BellmanFordShortestPath(Func<TEdge, TWeight>)

Initializes the algorithm with the function that reads an edge's weight.

public BellmanFordShortestPath(Func<TEdge, TWeight> weightSelector)

Parameters

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Exceptions

ArgumentNullException

weightSelector is null.

Methods

FindPath(IReadOnlyGraph<TVertex, TEdge>, TVertex, TVertex)

Finds the shortest path from source to target.

public ShortestPathResult<TVertex, TWeight> FindPath(IReadOnlyGraph<TVertex, TEdge> graph, TVertex source, TVertex target)

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to search.

source TVertex

The start vertex.

target TVertex

The end vertex.

Returns

ShortestPathResult<TVertex, TWeight>

The query result, unreachable when no path exists.

Exceptions

ArgumentException

Either endpoint is not in the graph.

NegativeCycleException

A negative cycle is reachable from source.

FindPathsFrom(IReadOnlyGraph<TVertex, TEdge>, TVertex)

Computes shortest paths from source to every reachable vertex in one run, for querying many targets without re-running the algorithm. Negative edge weights are supported.

public SingleSourceShortestPaths<TVertex, TWeight> FindPathsFrom(IReadOnlyGraph<TVertex, TEdge> graph, TVertex source)

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to search.

source TVertex

The start vertex.

Returns

SingleSourceShortestPaths<TVertex, TWeight>

A queryable single-source result.

Exceptions

ArgumentException

source is not in the graph.

NegativeCycleException

A negative cycle is reachable from source.

FindPathsFrom(IReadOnlyGraph<TVertex, TEdge>, TVertex, CancellationToken)

Computes shortest paths from source to every reachable vertex, observing cancellationToken between relaxation passes. Negative edge weights are supported.

public SingleSourceShortestPaths<TVertex, TWeight> FindPathsFrom(IReadOnlyGraph<TVertex, TEdge> graph, TVertex source, CancellationToken cancellationToken)

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to search.

source TVertex

The start vertex.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

SingleSourceShortestPaths<TVertex, TWeight>

A queryable single-source result.

Exceptions

ArgumentException

source is not in the graph.

NegativeCycleException

A negative cycle is reachable from source.

OperationCanceledException

The token was cancelled.