Class JohnsonAllShortestPaths<TVertex, TEdge, TWeight>

Namespace

Graph1x.Algorithms

Assembly

Graph1x.dll

Johnson's all-pairs shortest-path algorithm: one Bellman-Ford pass (from an implicit virtual source) establishes vertex potentials that make every reduced weight non-negative, then a Dijkstra run per source fills the distance table. On sparse graphs this is far cheaper than Floyd-Warshall's O(V³) while supporting the same negative edge weights; any negative cycle throws NegativeCycleException.

public sealed class JohnsonAllShortestPaths<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

JohnsonAllShortestPaths<TVertex, TEdge, TWeight>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Constructors

JohnsonAllShortestPaths(Func<TEdge, TWeight>)

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

public JohnsonAllShortestPaths(Func<TEdge, TWeight> weightSelector)

Parameters

weightSelector Func<TEdge, TWeight>

Maps an edge to its weight.

Exceptions

ArgumentNullException

weightSelector is null.

Methods

Compute(IReadOnlyGraph<TVertex, TEdge>)

Computes shortest paths between every pair of vertices.

public AllPairsShortestPaths<TVertex, TWeight> Compute(IReadOnlyGraph<TVertex, TEdge> graph)

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to analyze.

Returns

AllPairsShortestPaths<TVertex, TWeight>

A queryable all-pairs result.

Exceptions

NegativeCycleException

The graph contains a negative cycle.

Compute(IReadOnlyGraph<TVertex, TEdge>, CancellationToken)

Computes shortest paths between every pair of vertices, observing cancellationToken between per-source runs.

public AllPairsShortestPaths<TVertex, TWeight> Compute(IReadOnlyGraph<TVertex, TEdge> graph, CancellationToken cancellationToken)

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to analyze.

cancellationToken CancellationToken

Cancels the computation cooperatively.

Returns

AllPairsShortestPaths<TVertex, TWeight>

A queryable all-pairs result.

Exceptions

NegativeCycleException

The graph contains a negative cycle.

OperationCanceledException

The token was cancelled.

Compute(IReadOnlyGraph<TVertex, TEdge>, ParallelOptions)

Computes shortest paths between every pair of vertices, running the per-source Dijkstra passes in parallel. Results are identical to the sequential overload (each row is the same computation).

public AllPairsShortestPaths<TVertex, TWeight> Compute(IReadOnlyGraph<TVertex, TEdge> graph, ParallelOptions parallelOptions)

Parameters

graph IReadOnlyGraph<TVertex, TEdge>

The graph to analyze.

parallelOptions ParallelOptions

Degree of parallelism and cancellation.

Returns

AllPairsShortestPaths<TVertex, TWeight>

A queryable all-pairs result.

Exceptions

NegativeCycleException

The graph contains a negative cycle.

OperationCanceledException

The options' token was cancelled.