Class KShortestPaths<TWeight>

Namespace

AlgorithmsSW.EdgeWeightedDigraph

Assembly

AlgorithmsSW.dll

This is an implementation of (a modified) Dijkstra's algorithm that finds the k shortest paths between a source and a target.

[ExerciseReference(4, 4, 7)]
public class KShortestPaths<TWeight> : IKShortestPaths<TWeight> where TWeight : INumber<TWeight>

Type Parameters

TWeight

The type of the edge weights.

Inheritance

object

KShortestPaths<TWeight>

Implements

IKShortestPaths<TWeight>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

Applications.ApplyInterpolationRule<T, TBuffer>(TBuffer, Func<T, T, T>)

Applications.ApplyInterpolationRule<T, TBuffer>(TBuffer, Func<T, T, T>, int)

Applications.Interpolate<T, TBuffer>(TBuffer, Func<T, T, T>, int)

Applications.Substitute<T, TBuffer>(TBuffer, (T input, T[] output)[])

Comparable.ToComparable<T>(T, IComparer<T>)

Formatter.AsText<T>(T?)

Formatter.Describe<TLabel, TDescription>(TLabel, TDescription, string)

Formatter.Log<T>(T)

Formatter.Pretty<T>(T, params int[])

Remarks

Reference: https://en.wikipedia.org/wiki/K_shortest_path_routing.

Constructors

KShortestPaths(IReadOnlyEdgeWeightedDigraph<TWeight>, int, int, int)

Initializes a new instance of the KShortestPaths<TWeight> class.

public KShortestPaths(IReadOnlyEdgeWeightedDigraph<TWeight> graph, int source, int target, int k)

Parameters

graph IReadOnlyEdgeWeightedDigraph<TWeight>

The graph to find the shortest paths in.

source int

The source vertex.

target int

The target vertex.

k int

The number of shortest paths to find.

Methods

GetDistance(int)

Gets the distance of the kth shortest path between the source and target.

public TWeight GetDistance(int k)

Parameters

k int

The rank of the path whose distance to get.

Returns

TWeight

Exceptions

InvalidOperationException

No path exists with the given rank.

GetPath(int)

Gets the kth shortest path between the source and target.

public DirectedPath<TWeight> GetPath(int rank)

Parameters

rank int

The rank of the path to get.

Returns

DirectedPath<TWeight>

The kth shortest path.

Exceptions

InvalidOperationException

No path exists with the given rank.

HasPath(int)

Gets whether there is a path with the given rank.

public bool HasPath(int k)

Parameters

k int

The rank of the path.

Returns

bool