Method GetShortestPathCost

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

Calculate the cost of the shortest path from state start to state end, using the A* algorithm.

Declaration

public static TCost? GetShortestPathCost<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
TCost	The traversal 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 to a destination using GetShortestPathCost.

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
    .GetShortestPathCost<(int x, int y), double>(
        start,
        GetNeighbors,
        end);

Console.WriteLine($"cost: {result:N3}");

// This code produces the following output:
// cost: 4.006

Exceptions

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

| Edit this page View Source

GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost, TCost bestGuess)>>, TState, IEqualityComparer<TState>?, IComparer<TCost>?)

Calculate the cost of the shortest path from state start to state end, using the A* algorithm.

Declaration

public static TCost? GetShortestPathCost<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost, 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
TCost	The traversal 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

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.

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 to a destination using GetShortestPathCost.

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
    .GetShortestPathCost<(int x, int y), double>(
        start,
        GetNeighbors,
        end,
        new PointComparer(),
        null);

Console.WriteLine($"cost: {result:N3}");

// This code produces the following output:
// cost: 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.

| Edit this page View Source

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

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

Declaration

public static TCost? GetShortestPathCost<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
TCost	The traversal 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.

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 to a destination using GetShortestPathCost.

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
    .GetShortestPathCost<(int x, int y), double>(
        start,
        GetNeighbors,
        state => state == end);

Console.WriteLine($"cost: {result:N3}");

// This code produces the following output:
// cost: 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.

| Edit this page View Source

GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost, TCost bestGuess)>>, Func<TState, bool>, IEqualityComparer<TState>?, IComparer<TCost>?)

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

Declaration

public static TCost? GetShortestPathCost<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost, 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
TCost	The traversal 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

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.

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 to a destination using GetShortestPathCost.

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
    .GetShortestPathCost<(int x, int y), double>(
        start,
        GetNeighbors,
        state => new PointComparer().Equals(state, end),
        new PointComparer(),
        null);

Console.WriteLine($"cost: {result:N3}");

// This code produces the following output:
// cost: 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.

| Edit this page View Source

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

Calculate the cost of the shortest path from state start to state end, using Dijkstra's algorithm.

Declaration

public static TCost? GetShortestPathCost<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
TCost	The traversal 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 to a destination using GetShortestPathCost.

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
    .GetShortestPathCost<string, int>(
        "start",
        (state, cost) => map[state]
            .Select(x => (x.to, x.cost + cost)),
        "end");

Console.WriteLine($"cost: {result}");

// This code produces the following output:
// cost: 15

Exceptions

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

| Edit this page View Source

GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>>, TState, IEqualityComparer<TState>?, IComparer<TCost>?)

Calculate the cost of the shortest path from state start to state end, using Dijkstra's algorithm.

Declaration

public static TCost? GetShortestPathCost<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
TCost	The traversal 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

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.

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 to a destination using GetShortestPathCost.

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
    .GetShortestPathCost<string, int>(
        "start",
        (state, cost) => map[state]
            .Select(x => (x.to, x.cost + cost)),
        "end",
        StringComparer.OrdinalIgnoreCase,
        default);

Console.WriteLine($"cost: {result}");

// This code produces the following output:
// cost: 10

Exceptions

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

| Edit this page View Source

GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>>, Func<TState, bool>)

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

Declaration

public static TCost? GetShortestPathCost<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
TCost	The traversal 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.

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 to a destination using GetShortestPathCost.

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
    .GetShortestPathCost<(string id, int index), int>(
        ("start", 1),
        (state, cost) => map[state.id]
            .Select(x => (x.to, x.cost + cost)),
        x => x.id == "end");

Console.WriteLine($"cost: {result}");

// This code produces the following output:
// cost: 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.

| Edit this page View Source

GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>>, Func<TState, bool>, IEqualityComparer<TState>?, IComparer<TCost>?)

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

Declaration

public static TCost? GetShortestPathCost<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
TCost	The traversal 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

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.

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 to a destination using GetShortestPathCost.

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
    .GetShortestPathCost<(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($"cost: {result}");

// This code produces the following output:
// cost: 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.

Search Results for

Method GetShortestPathCost

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

Declaration

Parameters

Returns

Type Parameters

Remarks

Examples

Exceptions

GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost, TCost bestGuess)>>, TState, IEqualityComparer<TState>?, IComparer<TCost>?)

Declaration

Parameters

Returns

Type Parameters

Remarks

Examples

Exceptions

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

Declaration

Parameters

Returns

Type Parameters

Remarks

Examples

Exceptions

GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost, TCost bestGuess)>>, Func<TState, bool>, IEqualityComparer<TState>?, IComparer<TCost>?)

Declaration

Parameters

Returns

Type Parameters

Remarks

Examples

Exceptions

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

Declaration

Parameters

Returns

Type Parameters

Remarks

Examples

Exceptions

GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>>, TState, IEqualityComparer<TState>?, IComparer<TCost>?)

Declaration

Parameters

Returns

Type Parameters

Remarks

Examples

Exceptions

GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>>, Func<TState, bool>)

Declaration

Parameters

Returns

Type Parameters

Remarks

Examples

Exceptions

GetShortestPathCost<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>>, Func<TState, bool>, IEqualityComparer<TState>?, IComparer<TCost>?)

Declaration

Parameters

Returns

Type Parameters

Remarks

Examples

Exceptions