Method GetShortestPath

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

Find the shortest path from state start to state end, using Dijkstra's algorithm.

Declaration

public static ValueTask<IEnumerable<(TState nextState, TCost? cost)>> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>> getNeighbors, TState end, 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.
TState	end	The target state
CancellationToken	cancellationToken	The optional cancellation token to be used for cancelling the sequence at any time.

Returns

Type	Description
ValueTask<IEnumerable<(TState nextState, TCost cost)>>	The traversal path and cost of the shortest path from start to end.

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 end. 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.

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 will operate on an infinite map, however, performance will depend on how many states are required to be evaluated before reaching the target point.

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

This operator executes immediately.

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.
InvalidOperationException	The map is entirely explored and no path to end is found.

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

Find the shortest path from state start to state end, using Dijkstra's algorithm.

Declaration

public static ValueTask<IEnumerable<(TState state, TCost? cost)>> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>> getNeighbors, TState end, 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.
TState	end	The target 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<IEnumerable<(TState nextState, TCost cost)>>	The traversal path and cost of the shortest path from start to end.

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 end. 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.

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 will operate on an infinite map, however, performance will depend on how many states are required to be evaluated before reaching the target point.

This operator executes immediately.

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.
InvalidOperationException	The map is entirely explored and no path to end is found.

GetShortestPath<TState, TCost>(TState, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>>, Func<TState, ValueTask<bool>>, CancellationToken)

Find the shortest path from state start to a state that satisfies the conditions expressed by predicate, using Dijkstra's algorithm.

Declaration

public static ValueTask<IEnumerable<(TState nextState, TCost? cost)>> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>> getNeighbors, Func<TState, ValueTask<bool>> predicate, 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.
Func<TState, ValueTask<bool>>	predicate	The predicate that defines the conditions of the element to search for.
CancellationToken	cancellationToken	The optional cancellation token to be used for cancelling the sequence at any time.

Returns

Type	Description
ValueTask<IEnumerable<(TState nextState, TCost cost)>>	The traversal path and cost of the shortest path from start to a state that satisfies the conditions expressed by predicate.

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 a state that satisfies the conditions expressed by predicate. 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.

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 will operate on an infinite map, however, performance will depend on how many states are required to be evaluated before reaching the target point.

This operator executes immediately.

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.
InvalidOperationException	The map is entirely explored and no state that satisfies the conditions expressed by predicate is found.

GetShortestPath<TState, TCost>(TState, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>>, Func<TState, ValueTask<bool>>, IEqualityComparer<TState>?, IComparer<TCost>?, CancellationToken)

Find the shortest path from state start to a state that satisfies the conditions expressed by predicate, using Dijkstra's algorithm.

Declaration

public static ValueTask<IEnumerable<(TState state, TCost? cost)>> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost)>> getNeighbors, Func<TState, ValueTask<bool>> predicate, 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.
Func<TState, ValueTask<bool>>	predicate	The predicate that defines the conditions of the element to search for.
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<IEnumerable<(TState nextState, TCost cost)>>	The traversal path and cost of the shortest path from start to a state that satisfies the conditions expressed by predicate.

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 a state that satisfies the conditions expressed by predicate. 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.

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 will operate on an infinite map, however, performance will depend on how many states are required to be evaluated before reaching the target point.

This operator executes immediately.

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.
InvalidOperationException	The map is entirely explored and no state that satisfies the conditions expressed by predicate is found.

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

Find the shortest path from state start to state end, using the A* algorithm.

Declaration

public static ValueTask<IEnumerable<(TState nextState, TCost? cost)>> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost, TCost bestGuess)>> getNeighbors, TState end, 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, TCost bestGuess)>>	getNeighbors	A function that returns the neighbors for a given state; the total cost to get to that state based on the traversal cost at the current state; and the predicted or best-guess total (already traversed plus remaining) cost to get to end.
TState	end	The target state
CancellationToken	cancellationToken	The optional cancellation token to be used for cancelling the sequence at any time.

Returns

Type	Description
ValueTask<IEnumerable<(TState nextState, TCost cost)>>	The traversal path and cost of the shortest path from start to end.

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 the A* algorithm to explore a map and find the shortest path from start to end. An UpdatablePriorityQueue<TElement, TPriority> is used to manage the list of TStates to process, to reduce the computation cost of this operator. Overall performance of this method will depend on the reliability of the best-guess cost provided by getNeighbors.

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.

The A* 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 will operate on an infinite map, however, performance will depend on how many states are required to be evaluated before reaching the target point.

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

This operator executes immediately.

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.
InvalidOperationException	The map is entirely explored and no path to end is found.

GetShortestPath<TState, TCost>(TState, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost traversed, TCost bestGuess)>>, TState, IEqualityComparer<TState>?, IComparer<TCost>?, CancellationToken)

Find the shortest path from state start to state end, using the A* algorithm.

Declaration

public static ValueTask<IEnumerable<(TState nextState, TCost? cost)>> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost traversed, TCost bestGuess)>> getNeighbors, TState end, 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, TCost bestGuess)>>	getNeighbors	A function that returns the neighbors for a given state; the total cost to get to that state based on the traversal cost at the current state; and the predicted or best-guess total (already traversed plus remaining) cost to get to end.
TState	end	The target 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<IEnumerable<(TState nextState, TCost cost)>>	The traversal path and cost of the shortest path from start to end.

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 the A* algorithm to explore a map and find the shortest path from start to end. An UpdatablePriorityQueue<TElement, TPriority> is used to manage the list of TStates to process, to reduce the computation cost of this operator. Overall performance of this method will depend on the reliability of the best-guess cost provided by getNeighbors.

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.

The A* 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 will operate on an infinite map, however, performance will depend on how many states are required to be evaluated before reaching the target point.

This operator executes immediately.

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.
InvalidOperationException	The map is entirely explored and no path to end is found.

GetShortestPath<TState, TCost>(TState, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost, TCost bestGuess)>>, Func<TState, ValueTask<bool>>, CancellationToken)

Find the shortest path from state start to a state that satisfies the conditions expressed by predicate, using the A* algorithm.

Declaration

public static ValueTask<IEnumerable<(TState nextState, TCost? cost)>> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost cost, TCost bestGuess)>> getNeighbors, Func<TState, ValueTask<bool>> predicate, 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, TCost bestGuess)>>	getNeighbors	A function that returns the neighbors for a given state; the total cost to get to that state based on the traversal cost at the current state; and the predicted or best-guess total (already traversed plus remaining) cost to get to a state that satisfies the conditions expressed by predicate.
Func<TState, ValueTask<bool>>	predicate	The predicate that defines the conditions of the element to search for.
CancellationToken	cancellationToken	The optional cancellation token to be used for cancelling the sequence at any time.

Returns

Type	Description
ValueTask<IEnumerable<(TState nextState, TCost cost)>>	The traversal path and cost of the shortest path from start to a state that satisfies the conditions expressed by predicate.

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 the A* algorithm to explore a map and find the shortest path from start to a state that satisfies the conditions expressed by predicate. An UpdatablePriorityQueue<TElement, TPriority> is used to manage the list of TStates to process, to reduce the computation cost of this operator. Overall performance of this method will depend on the reliability of the best-guess cost provided by getNeighbors.

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.

The A* 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 will operate on an infinite map, however, performance will depend on how many states are required to be evaluated before reaching the target point.

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

This operator executes immediately.

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.
InvalidOperationException	The map is entirely explored and no state that satisfies the conditions expressed by predicate is found.

GetShortestPath<TState, TCost>(TState, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost traversed, TCost bestGuess)>>, Func<TState, ValueTask<bool>>, IEqualityComparer<TState>?, IComparer<TCost>?, CancellationToken)

Find the shortest path from state start to a state that satisfies the conditions expressed by predicate, using the A* algorithm.

Declaration

public static ValueTask<IEnumerable<(TState nextState, TCost? cost)>> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IAsyncEnumerable<(TState nextState, TCost traversed, TCost bestGuess)>> getNeighbors, Func<TState, ValueTask<bool>> predicate, 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, TCost bestGuess)>>	getNeighbors	A function that returns the neighbors for a given state; the total cost to get to that state based on the traversal cost at the current state; and the predicted or best-guess total (already traversed plus remaining) cost to get to a state that satisfies the conditions expressed by predicate.
Func<TState, ValueTask<bool>>	predicate	The predicate that defines the conditions of the element to search for.
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<IEnumerable<(TState nextState, TCost cost)>>	The traversal path and cost of the shortest path from start to a state that satisfies the conditions expressed by predicate.

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 the A* algorithm to explore a map and find the shortest path from start to a state that satisfies the conditions expressed by predicate. An UpdatablePriorityQueue<TElement, TPriority> is used to manage the list of TStates to process, to reduce the computation cost of this operator. Overall performance of this method will depend on the reliability of the best-guess cost provided by getNeighbors.

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.

The A* 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 will operate on an infinite map, however, performance will depend on how many states are required to be evaluated before reaching the target point.

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

This operator executes immediately.

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.
InvalidOperationException	The map is entirely explored and no state that satisfies the conditions expressed by predicate is found.