Dijkstra Class

Class for calculating distances from a vertex/node to any other vertex/node in the graph, using the Dijstra algorithm.

Before calling Start, you must initialize the algorithm by calling either Initialize(Int32), or Initialize followed by at least one call to SetSource(Int32, Double).

The algorithm uses a binary heap as priority queue, hence the running time of the Dijkstra algorithm is O((E+V)*log(V))

Inheritance Hierarchy

SystemObject
DHI.Mike1D.Generic.GraphDijkstra

Namespace: DHI.Mike1D.Generic.Graph
Assembly: DHI.Mike1D.Generic (in DHI.Mike1D.Generic.dll) Version: 16.0.0.0 (11.1.1.1111)

Syntax

Copy

public class Dijkstra

The Dijkstra type exposes the following members.

Constructors

	Name	Description
	Dijkstra	Constructor, providing the graph to use.

Top

Properties

	Name	Description
	Distances	Distances to all vertices from source vertex. The value double.MaxValue indicates that the vertex can not be reached from the source vertices, or that the algorithm has been manually stopped before reaching the vertix.
	Predecessor	Predecessors index for each vertex it specifies the previous vertex in the path from source to target. The value -1 indicates that the vertex can not be reached from the source vertices, or that the algorithm has been manually stopped before reaching the vertix, or the vertex is a source vertex.
	PredecessorSource	Predecessor source index, for each vertex it specifies the predecessor source, i.e. which source this vertex has the shortest path from. This is only relevant if more than one source is specified. Enable by setting the UsePredecessorSource flag. If the flag is not enabled, this array will be null. The value -1 indicates that the vertex can not be reached from the source vertices, or that the algorithm has been manually stopped before reaching the vertix.
	Stop	User defined stopping criteria. If not set, distances to all vertices are calculated.
	UsePredecessorSource	Flag defining whether to calculate and store the PredecessorSource Must be set before calling Initialize
	Visited	Array of visited vertices. When no stopping criteria is set (using the Stop property), the non-visited nodes are not reachable from the source nodes. If a stopping criteria is set, only nodes with the visited flag set to true has a shortest distance correctly calculated.

Top

Methods

	Name	Description
	Equals	Determines whether the specified object is equal to the current object. (Inherited from Object.)
	Finalize	Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection. (Inherited from Object.)
	GetHashCode	Serves as a hash function for a particular type. (Inherited from Object.)
	GetType	Gets the Type of the current instance. (Inherited from Object.)
	Initialize	Initialize algorithm. Must be called before the Dijkstra algorithm is started
	Initialize(Int32)	Initialize algorithm. Must be called before the Dijkstra algorithm is started. Sets the sourceVertex as the source for the distance calculations.
	MemberwiseClone	Creates a shallow copy of the current Object. (Inherited from Object.)
	SetSource	Sets a vertex as a source for the calculations, providing its "distance" from the "original" source in case that does not exactly co-inside with the vertex. It is allowed to set more than one source.
	SetStopMaxDistance	Setup up stop criteria that stops the Dijstra algorithm when when distances exceed a provided distance.
	SetStopTargetVertex	Setup up stop criteria that stops the Dijstra algorithm when a target vertex has been reached (visited).
	Start	Start the algorithm
	ToString	Returns a string that represents the current object. (Inherited from Object.)

Top

Examples

This sample shows how to use the Dijkstra class

Copy

Dijkstra dijkstra = new Dijkstra(someGraph);
// Set vertex number 6 (index 5) as source vertex
dijkstra.Initialize(5);
dijkstra.Start();

Reference

DHI.Mike1D.Generic.Graph Namespace