Class DijkstraSourceSink<TWeight>

Namespace

AlgorithmsSW.EdgeWeightedDigraph

Assembly

AlgorithmsSW.dll

A modified version of Dijkstra's algorithm that finds the shortest path from a source to a sink.

[ExerciseReference(4, 4, 23)]
public class DijkstraSourceSink<TWeight> where TWeight : INumber<TWeight>, IMinMaxValue<TWeight>

Type Parameters

TWeight

Inheritance

object

DijkstraSourceSink<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

This implementation can be faster than vanilla Dijkstra since we can stop early once we processed the sink.

Constructors

DijkstraSourceSink(IEdgeWeightedDigraph<TWeight>, int, int)

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

public DijkstraSourceSink(IEdgeWeightedDigraph<TWeight> graph, int source, int sink)

Parameters

graph IEdgeWeightedDigraph<TWeight>

The graph to find the shortest path in.

source int

The source vertex to find the shortest path from.

sink int

The sink vertex to find the shortest path to.

Exceptions

ArgumentException

graph contains negative weights.

Properties

Distance

Gets the distance from the source to the sink.

public TWeight Distance { get; }

Property Value

TWeight

Exceptions

InvalidOperationException

PathExists is false.

Path

Gets the path from the source to the sink.

public IReadonlyRandomAccessList<DirectedEdge<TWeight>>? Path { get; }

Property Value

IReadonlyRandomAccessList<DirectedEdge<TWeight>>

Exceptions

InvalidOperationException

PathExists is false.

PathExists

Gets a value indicating whether a path exists from the source to the sink.

public bool PathExists { get; }

Property Value

bool