Method GetShortestPaths

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

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

Declaration

public static IReadOnlyDictionary<TState, (TState? previousState, TCost? cost)> GetShortestPaths<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>> getNeighbors) 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.

Returns

Type	Description
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?, IEnumerable<(TState nextState, TCost cost)>>, TState) and GetShortestPath<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>>, TState) will work work on infinite maps, this method will execute an infinite loop on infinite maps. This is because this method will attempt 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.

Examples

The following code example demonstrates how to use Dijkstra's algorithm to build a distance map using GetShortestPaths.

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

foreach (var (key, (from, cost)) in result)
{
    Console.WriteLine($"[{key}] = (from: {from}, totalCost: {cost})");
}

// This code produces the following output:
// [start] = (from: , totalCost: 0)
// [a] = (from: start, totalCost: 1)
// [b] = (from: a, totalCost: 3)
// [c] = (from: b, totalCost: 6)
// [END] = (from: start, totalCost: 10)
// [d] = (from: c, totalCost: 10)
// [A] = (from: start, totalCost: 10)
// [end] = (from: d, totalCost: 15)
// [B] = (from: A, totalCost: 30)
// [C] = (from: B, totalCost: 60)
// [D] = (from: C, totalCost: 100)

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.

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

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

Declaration

public static IReadOnlyDictionary<TState, (TState? previousState, TCost? cost)> GetShortestPaths<TState, TCost>(TState start, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>> getNeighbors, 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.
IEqualityComparer<TState>	stateComparer	A custom equality comparer for TState
IComparer<TCost>	costComparer	A custom comparer for TCost

Returns

Type	Description
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?, IEnumerable<(TState nextState, TCost cost)>>, TState) and GetShortestPath<TState, TCost>(TState, Func<TState, TCost?, IEnumerable<(TState nextState, TCost cost)>>, TState) will work work on infinite maps, this method will execute an infinite loop on infinite maps. This is because this method will attempt 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.

Examples

The following code example demonstrates how to use Dijkstra's algorithm to build a distance map using GetShortestPaths.

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

foreach (var (key, (from, cost)) in result)
{
    Console.WriteLine($"[{key}] = (from: {from}, totalCost: {cost})");
}

// This code produces the following output:
// [start] = (from: , totalCost: 0)
// [a] = (from: start, totalCost: 1)
// [b] = (from: a, totalCost: 3)
// [c] = (from: b, totalCost: 6)
// [END] = (from: start, totalCost: 10)
// [d] = (from: c, totalCost: 10)

Exceptions

Type	Condition
ArgumentNullException	getNeighbors is null.