Method GetShortestPath

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

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

Declaration

public static IEnumerable<(TState nextState, TCost? cost)> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost, TCost bestGuess)>> getNeighbors, TState end) where TState : notnull where TCost : notnull

Parameters

Type	Name	Description
TState	start	The starting state
Func<TState, TCost, IEnumerable<(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

Returns

Type	Description
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.

Examples

The following code example demonstrates how to use A* to find the shortest path using GetShortestPath.

var start = (x: 0, y: 0);
var end = (x: 2, y: 2);
((int x, int y) p, double cost, double bestGuess) GetNeighbor((int x, int y) p, double newCost)
{
    var xD = p.x - end.x;
    var yD = p.y - end.y;
    var dist = Math.Sqrt((xD * xD) + (yD * yD));
    return (p, newCost, newCost + dist);
}

IEnumerable<((int x, int y) p, double cost, double bestGuess)> GetNeighbors((int x, int y) p, double cost)
{
    yield return GetNeighbor((p.x + 1, p.y), cost + 1.001d);
    yield return GetNeighbor((p.x, p.y + 1), cost + 1.002d);
    yield return GetNeighbor((p.x - 1, p.y), cost + 1.003d);
    yield return GetNeighbor((p.x, p.y - 1), cost + 1.004d);
}

// Find the shortest path from start to end
var result = SuperEnumerable
    .GetShortestPath<(int x, int y), double>(
        start,
        GetNeighbors,
        end);

Console.WriteLine(string.Join(" -> ", result.Select(x => $"({x.nextState}, {x.cost:N3})")));

// This code produces the following output:
// ((0, 0), 0.000) -> ((1, 0), 1.001) -> ((2, 0), 2.002) -> ((2, 1), 3.004) -> ((2, 2), 4.006)

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?, IEnumerable<(TState nextState, TCost traversed, TCost bestGuess)>>, TState, IEqualityComparer<TState>?, IComparer<TCost>?)

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

Declaration

public static IEnumerable<(TState nextState, TCost? cost)> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost traversed, TCost bestGuess)>> getNeighbors, TState end, IEqualityComparer<TState>? stateComparer, IComparer<TCost>? costComparer) where TState : notnull where TCost : notnull

Parameters

Type	Name	Description
TState	start	The starting state
Func<TState, TCost, IEnumerable<(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

Returns

Type	Description
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.

Examples

The following code example demonstrates how to use A* to find the shortest path using GetShortestPath.

var start = (x: 0, y: 0);
var end = (x: -2, y: -2);
((int x, int y) p, double cost, double bestGuess) GetNeighbor((int x, int y) p, double newCost)
{
    var xD = p.x - end.x;
    var yD = p.y - end.y;
    var dist = Math.Sqrt((xD * xD) + (yD * yD));
    return (p, newCost, newCost + dist);
}

IEnumerable<((int x, int y) p, double cost, double bestGuess)> GetNeighbors((int x, int y) p, double cost)
{
    yield return GetNeighbor((p.x + 1, p.y), cost + 1.001d);
    yield return GetNeighbor((p.x, p.y + 1), cost + 1.002d);
    yield return GetNeighbor((p.x - 1, p.y), cost + 1.003d);
    yield return GetNeighbor((p.x, p.y - 1), cost + 1.004d);
}

// Find the shortest path from start to end
var result = SuperEnumerable
    .GetShortestPath<(int x, int y), double>(
        start,
        GetNeighbors,
        end,
        new PointComparer(),
        null);

Console.WriteLine(string.Join(" -> ", result.Select(x => $"({x.nextState}, {x.cost:N3})")));

// This code produces the following output:
// ((0, 0), 0.000) -> ((-1, 0), 1.003) -> ((-1, -1), 2.007) -> ((-2, -1), 3.010) -> ((-2, -2), 4.014)

class PointComparer : IEqualityComparer<(int x, int y)>
{
    public bool Equals((int x, int y) x, (int x, int y) y) =>
        ManhattanDistance(x) == ManhattanDistance(y);

    public int GetHashCode((int x, int y) obj) =>
        ManhattanDistance(obj).GetHashCode();

    private static double ManhattanDistance((int x, int y) obj) =>
        Math.Sqrt((obj.x * obj.x) + (obj.y * obj.y));
}

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?, IEnumerable<(TState nextState, TCost cost, TCost bestGuess)>>, Func<TState, bool>)

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

Declaration

public static IEnumerable<(TState nextState, TCost? cost)> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost, TCost bestGuess)>> getNeighbors, Func<TState, bool> predicate) where TState : notnull where TCost : notnull

Parameters

Type	Name	Description
TState	start	The starting state
Func<TState, TCost, IEnumerable<(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, bool>	predicate	The predicate that defines the conditions of the element to search for.

Returns

Type	Description
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.

Examples

The following code example demonstrates how to use A* to find the shortest path using GetShortestPath.

var start = (x: 0, y: 0);
var end = (x: 2, y: 2);
((int x, int y) p, double cost, double bestGuess) GetNeighbor((int x, int y) p, double newCost)
{
    var xD = p.x - end.x;
    var yD = p.y - end.y;
    var dist = Math.Sqrt((xD * xD) + (yD * yD));
    return (p, newCost, newCost + dist);
}

IEnumerable<((int x, int y) p, double cost, double bestGuess)> GetNeighbors((int x, int y) p, double cost)
{
    yield return GetNeighbor((p.x + 1, p.y), cost + 1.001d);
    yield return GetNeighbor((p.x, p.y + 1), cost + 1.002d);
    yield return GetNeighbor((p.x - 1, p.y), cost + 1.003d);
    yield return GetNeighbor((p.x, p.y - 1), cost + 1.004d);
}

// Find the shortest path from start to end
var result = SuperEnumerable
    .GetShortestPath<(int x, int y), double>(
        start,
        GetNeighbors,
        state => state == end);

Console.WriteLine(string.Join(" -> ", result.Select(x => $"({x.nextState}, {x.cost:N3})")));

// This code produces the following output:
// ((0, 0), 0.000) -> ((1, 0), 1.001) -> ((2, 0), 2.002) -> ((2, 1), 3.004) -> ((2, 2), 4.006)

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?, IEnumerable<(TState nextState, TCost traversed, TCost bestGuess)>>, Func<TState, bool>, IEqualityComparer<TState>?, IComparer<TCost>?)

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

Declaration

public static IEnumerable<(TState nextState, TCost? cost)> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost traversed, TCost bestGuess)>> getNeighbors, Func<TState, bool> predicate, IEqualityComparer<TState>? stateComparer, IComparer<TCost>? costComparer) where TState : notnull where TCost : notnull

Parameters

Type	Name	Description
TState	start	The starting state
Func<TState, TCost, IEnumerable<(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, 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

Returns

Type	Description
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 operator executes immediately.

Examples

The following code example demonstrates how to use A* to find the shortest path using GetShortestPath.

var start = (x: 0, y: 0);
var end = (x: -2, y: -2);
((int x, int y) p, double cost, double bestGuess) GetNeighbor((int x, int y) p, double newCost)
{
    var xD = p.x - end.x;
    var yD = p.y - end.y;
    var dist = Math.Sqrt((xD * xD) + (yD * yD));
    return (p, newCost, newCost + dist);
}

IEnumerable<((int x, int y) p, double cost, double bestGuess)> GetNeighbors((int x, int y) p, double cost)
{
    yield return GetNeighbor((p.x + 1, p.y), cost + 1.001d);
    yield return GetNeighbor((p.x, p.y + 1), cost + 1.002d);
    yield return GetNeighbor((p.x - 1, p.y), cost + 1.003d);
    yield return GetNeighbor((p.x, p.y - 1), cost + 1.004d);
}

// Find the shortest path from start to end
var result = SuperEnumerable
    .GetShortestPath<(int x, int y), double>(
        start,
        GetNeighbors,
        state => new PointComparer().Equals(state, end),
        new PointComparer(),
        null);

Console.WriteLine(string.Join(" -> ", result.Select(x => $"({x.nextState}, {x.cost:N3})")));

// This code produces the following output:
// ((0, 0), 0.000) -> ((-1, 0), 1.003) -> ((-1, -1), 2.007) -> ((-2, -1), 3.010) -> ((-2, -2), 4.014)

class PointComparer : IEqualityComparer<(int x, int y)>
{
    public bool Equals((int x, int y) x, (int x, int y) y) =>
        ManhattanDistance(x) == ManhattanDistance(y);

    public int GetHashCode((int x, int y) obj) =>
        ManhattanDistance(obj).GetHashCode();

    private static double ManhattanDistance((int x, int y) obj) =>
        Math.Sqrt((obj.x * obj.x) + (obj.y * obj.y));
}

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?, IEnumerable<(TState nextState, TCost cost)>>, TState)

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

Declaration

public static IEnumerable<(TState nextState, TCost? cost)> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>> getNeighbors, TState end) where TState : notnull where TCost : notnull

Parameters

Type	Name	Description
TState	start	The starting state
Func<TState, TCost, IEnumerable<(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

Returns

Type	Description
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.

Examples

The following code example demonstrates how to use Dijkstra's algorithm to find the shortest path using GetShortestPath.

var costs =
    new[]
    {
        (from: "start", to: "a", cost: 1),
        (from: "a", to: "b", cost: 2),
        (from: "b", to: "c", cost: 3),
        (from: "c", to: "d", cost: 4),
        (from: "d", to: "end", cost: 5),
        (from: "start", to: "A", cost: 10),
        (from: "A", to: "B", cost: 20),
        (from: "B", to: "C", cost: 30),
        (from: "C", to: "D", cost: 40),
        (from: "D", to: "end", cost: 50),
        (from: "start", to: "END", cost: 10),
        (from: "start", to: "END", cost: 1000),
    };
var map = costs
    .Concat(costs.Select(x => (from: x.to, to: x.from, x.cost)))
    .Where(x =>
        x.to != "start"
        && x.from != "end")
    .ToLookup(x => x.from, x => (x.to, x.cost));

// Find the shortest path from start to end
var result = SuperEnumerable
    .GetShortestPath<string, int>(
        "start",
        (state, cost) => map[state]
            .Select(x => (x.to, x.cost + cost)),
        "end");

Console.WriteLine(string.Join(" -> ", result));

// This code produces the following output:
// (start, 0) -> (a, 1) -> (b, 3) -> (c, 6) -> (d, 10) -> (end, 15)

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?, IEnumerable<(TState nextState, TCost cost)>>, TState, IEqualityComparer<TState>?, IComparer<TCost>?)

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

Declaration

public static IEnumerable<(TState state, TCost? cost)> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>> getNeighbors, TState end, IEqualityComparer<TState>? stateComparer, IComparer<TCost>? costComparer) where TState : notnull where TCost : notnull

Parameters

Type	Name	Description
TState	start	The starting state
Func<TState, TCost, IEnumerable<(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

Returns

Type	Description
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.

Examples

The following code example demonstrates how to use Dijkstra's algorithm to find the shortest path using GetShortestPath.

var costs =
    new[]
    {
        (from: "start", to: "a", cost: 1),
        (from: "a", to: "b", cost: 2),
        (from: "b", to: "c", cost: 3),
        (from: "c", to: "d", cost: 4),
        (from: "d", to: "end", cost: 5),
        (from: "start", to: "A", cost: 10),
        (from: "A", to: "B", cost: 20),
        (from: "B", to: "C", cost: 30),
        (from: "C", to: "D", cost: 40),
        (from: "D", to: "end", cost: 50),
        (from: "start", to: "END", cost: 10),
        (from: "start", to: "END", cost: 1000),
    };
var map = costs
    .Concat(costs.Select(x => (from: x.to, to: x.from, x.cost)))
    .Where(x =>
        x.to != "start"
        && x.from != "end")
    .ToLookup(x => x.from, x => (x.to, x.cost), StringComparer.OrdinalIgnoreCase);

// Find the shortest path from start to end
var result = SuperEnumerable
    .GetShortestPath<string, int>(
        "start",
        (state, cost) => map[state]
            .Select(x => (x.to, x.cost + cost)),
        "end",
        StringComparer.OrdinalIgnoreCase,
        default);

Console.WriteLine(string.Join(" -> ", result));

// This code produces the following output:
// (start, 0) -> (END, 10)

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?, IEnumerable<(TState nextState, TCost cost)>>, Func<TState, bool>)

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

Declaration

public static IEnumerable<(TState nextState, TCost? cost)> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>> getNeighbors, Func<TState, bool> predicate) where TState : notnull where TCost : notnull

Parameters

Type	Name	Description
TState	start	The starting state
Func<TState, TCost, IEnumerable<(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, bool>	predicate	The predicate that defines the conditions of the element to search for.

Returns

Type	Description
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 method uses Default to compare TStates and Default to compare traversal TCosts.

This operator executes immediately.

Examples

The following code example demonstrates how to use Dijkstra's algorithm to find the shortest path using GetShortestPath.

var costs =
    new[]
    {
        (from: (id: "start", index: 1), to: (id: "a", index: 2), cost: 1),
        (from: (id: "a", index: 2), to: (id: "b", index: 3), cost: 2),
        (from: (id: "b", index: 3), to: (id: "c", index: 3), cost: 3),
        (from: (id: "c", index: 3), to: (id: "d", index: 4), cost: 4),
        (from: (id: "d", index: 4), to: (id: "end", index: 5), cost: 5),
        (from: (id: "start", index: 1), to: (id: "A", index: 6), cost: 10),
        (from: (id: "A", index: 6), to: (id: "B", index: 7), cost: 20),
        (from: (id: "B", index: 7), to: (id: "C", index: 8), cost: 30),
        (from: (id: "C", index: 8), to: (id: "D", index: 9), cost: 40),
        (from: (id: "D", index: 9), to: (id: "end", index: 5), cost: 50),
        (from: (id: "start", index: 1), to: (id: "END", index: 10), cost: 10),
        (from: (id: "start", index: 1), to: (id: "END", index: 10), cost: 1000),
    };
var map = costs
    .Concat(costs.Select(x => (from: x.to, to: x.from, x.cost)))
    .Where(x =>
        x.to.id != "start"
        && x.from.id != "end")
    .ToLookup(x => x.from.id, x => (x.to, x.cost));

// Find the shortest path from start to end
var result = SuperEnumerable
    .GetShortestPath<(string id, int index), int>(
        ("start", 1),
        (state, cost) => map[state.id]
            .Select(x => (x.to, x.cost + cost)),
        x => x.id.Equals("end", StringComparison.OrdinalIgnoreCase));

Console.WriteLine(string.Join(" -> ", result));

// This code produces the following output:
// ((start, 1), 0) -> ((a, 2), 1) -> ((b, 3), 3) -> ((c, 3), 6) -> ((d, 4), 10) -> ((end, 5), 15)

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?, IEnumerable<(TState nextState, TCost cost)>>, Func<TState, bool>, IEqualityComparer<TState>?, IComparer<TCost>?)

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

Declaration

public static IEnumerable<(TState state, TCost? cost)> GetShortestPath<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>> getNeighbors, Func<TState, bool> predicate, IEqualityComparer<TState>? stateComparer, IComparer<TCost>? costComparer) where TState : notnull where TCost : notnull

Parameters

Type	Name	Description
TState	start	The starting state
Func<TState, TCost, IEnumerable<(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, 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

Returns

Type	Description
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.

Examples

The following code example demonstrates how to use Dijkstra's algorithm to find the shortest path using GetShortestPath.

var costs =
    new[]
    {
        (from: (id: "start", index: 1), to: (id: "a", index: 2), cost: 1),
        (from: (id: "a", index: 2), to: (id: "b", index: 3), cost: 2),
        (from: (id: "b", index: 3), to: (id: "c", index: 3), cost: 3),
        (from: (id: "c", index: 3), to: (id: "d", index: 4), cost: 4),
        (from: (id: "d", index: 4), to: (id: "end", index: 5), cost: 5),
        (from: (id: "start", index: 1), to: (id: "A", index: 6), cost: 10),
        (from: (id: "A", index: 6), to: (id: "B", index: 7), cost: 20),
        (from: (id: "B", index: 7), to: (id: "C", index: 8), cost: 30),
        (from: (id: "C", index: 8), to: (id: "D", index: 9), cost: 40),
        (from: (id: "D", index: 9), to: (id: "end", index: 5), cost: 50),
        (from: (id: "start", index: 1), to: (id: "END", index: 10), cost: 10),
        (from: (id: "start", index: 1), to: (id: "END", index: 10), cost: 1000),
    };
var map = costs
    .Concat(costs.Select(x => (from: x.to, to: x.from, x.cost)))
    .Where(x =>
        x.to.id != "start"
        && x.from.id != "end")
    .ToLookup(x => x.from.id, x => (x.to, x.cost), StringComparer.OrdinalIgnoreCase);

// Find the shortest path from start to end
var result = SuperEnumerable
    .GetShortestPath<(string id, int index), int>(
        ("start", 1),
        (state, cost) => map[state.id]
            .Select(x => (x.to, x.cost + cost)),
        x => x.id.Equals("end", StringComparison.OrdinalIgnoreCase),
        new StateComparer(),
        default);

Console.WriteLine(string.Join(" -> ", result));

// This code produces the following output:
// ((start, 1), 0) -> ((END, 10), 10)

class StateComparer : IEqualityComparer<(string id, int index)>
{
    public bool Equals((string id, int index) x, (string id, int index) y) =>
        StringComparer.OrdinalIgnoreCase.Equals(x.id, y.id);

    public int GetHashCode((string id, int index) obj) =>
        StringComparer.OrdinalIgnoreCase.GetHashCode(obj.id);
}

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.