Method GetShortestPaths

GetShortestPaths<TState, TCost>(TState, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>>, CancellationToken)

Find the shortest path from state start to every other TState in the map, using Dijkstra's algorithm.

Declaration

public static ValueTask<IReadOnlyDictionary<TState, (TState? previousState, TCost? cost)>> GetShortestPaths<TState, TCost>(TState start, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>> getNeighbors, CancellationToken cancellationToken = default) where TState : notnull where TCost : notnull

Parameters

Type	Name	Description
TState	start	The starting state
Func<TState, TCost, IAsyncEnumerable<(TState nextState, TCost cost)>>	getNeighbors	A function that returns the neighbors for a given state and the total cost to get to that state based on the traversal cost at the current state.
CancellationToken	cancellationToken	The optional cancellation token to be used for cancelling the sequence at any time.

Returns

Type	Description
ValueTask<IReadOnlyDictionary<TState, (TState previousState, TCost cost)>>	A map that contains, for every TState, the previous TState in the shortest path from start to this TState, as well as the total cost to travel from start to this TState.

Type Parameters

Name	Description
TState	The type of each state in the map
TCost	The type of the cost to traverse between states

Remarks

This method uses Dijkstra's algorithm to explore a map and find the shortest path from start to every other TState in the map. An UpdatablePriorityQueue<TElement, TPriority> is used to manage the list of TStates to process, to reduce the computation cost of this operator.

Loops and cycles are automatically detected and handled correctly by this operator; only the cheapest path to a given TState is used, and other paths (including loops) are discarded.

While GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>>, TState, CancellationToken) and GetShortestPath<TState, TCost>(TState, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>>, TState, CancellationToken) will work work on infinite maps, this method will execute an infinite loop on infinite maps. This is because this method will attemp to visit every point in the map. This method will terminate only when any points returned by getNeighbors have all already been visited.

Dijkstra's algorithm assumes that all costs are positive, that is to say, that it is not possible to go a negative distance from one state to the next. Violating this assumption will have undefined behavior.

This method uses Default to compare TStates and Default to compare traversal TCosts.

This operator executes immediately.

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.

GetShortestPaths<TState, TCost>(TState, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>>, IEqualityComparer<TState>?, IComparer<TCost>?, CancellationToken)

Find the shortest path from state start to every other TState in the map, using Dijkstra's algorithm.

Declaration

public static ValueTask<IReadOnlyDictionary<TState, (TState? previousState, TCost? cost)>> GetShortestPaths<TState, TCost>(TState start, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>> getNeighbors, IEqualityComparer<TState>? stateComparer, IComparer<TCost>? costComparer, CancellationToken cancellationToken = default) where TState : notnull where TCost : notnull

Parameters

Type	Name	Description
TState	start	The starting state
Func<TState, TCost, IAsyncEnumerable<(TState nextState, TCost cost)>>	getNeighbors	A function that returns the neighbors for a given state and the total cost to get to that state based on the traversal cost at the current state.
IEqualityComparer<TState>	stateComparer	A custom equality comparer for TState
IComparer<TCost>	costComparer	A custom comparer for TCost
CancellationToken	cancellationToken	The optional cancellation token to be used for cancelling the sequence at any time.

Returns

Type	Description
ValueTask<IReadOnlyDictionary<TState, (TState previousState, TCost cost)>>	A map that contains, for every TState, the previous TState in the shortest path from start to this TState, as well as the total cost to travel from start to this TState.

Type Parameters

Name	Description
TState	The type of each state in the map
TCost	The type of the cost to traverse between states

Remarks

This method uses Dijkstra's algorithm to explore a map and find the shortest path from start to every other TState in the map. An UpdatablePriorityQueue<TElement, TPriority> is used to manage the list of TStates to process, to reduce the computation cost of this operator.

Loops and cycles are automatically detected and handled correctly by this operator; only the cheapest path to a given TState is used, and other paths (including loops) are discarded.

While GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>>, TState, CancellationToken) and GetShortestPath<TState, TCost>(TState, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>>, TState, CancellationToken) will work work on infinite maps, this method will execute an infinite loop on infinite maps. This is because this method will attemp to visit every point in the map. This method will terminate only when any points returned by getNeighbors have all already been visited.

Dijkstra's algorithm assumes that all costs are positive, that is to say, that it is not possible to go a negative distance from one state to the next. Violating this assumption will have undefined behavior.

This operator executes immediately.

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.