Click or drag to resize

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: 19.0.0.0 (11.1.1.1111)
Syntax
public class Dijkstra

The Dijkstra type exposes the following members.

Constructors
  NameDescription
Public methodDijkstra
Constructor, providing the graph to use.
Top
Properties
  NameDescription
Public propertyDistances
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.

Public propertyPredecessor
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.

Public propertyPredecessorSource
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.

Public propertyStop
User defined stopping criteria. When node i has been visited (distance has been calculated for node), return true to stop.

If not set, distances to all vertices are calculated.

Public propertyUsePredecessorSource
Flag defining whether to calculate and store the PredecessorSource

Must be set before calling Initialize

Public propertyVisited
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.

Public propertyVisitEdge
User defined criteria of whether to visit edge. If returning false, this edge is disregarded.

If not set, all edges are considered.

Top
Methods
  NameDescription
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Public methodInitialize
Initialize algorithm. Must be called before the Dijkstra algorithm is started
Public methodInitialize(Int32)
Initialize algorithm. Must be called before the Dijkstra algorithm is started.

Sets the sourceVertex as the source for the distance calculations.

Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Public methodSetSource
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.

Public methodSetStopMaxDistance
Setup stop criteria that stops the Dijstra algorithm when when distances exceed a provided distance.
Public methodSetStopTargetVertex
Setup up stop criteria that stops the Dijstra algorithm when a target vertex has been reached (visited).
Public methodStart
Start the algorithm
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Top
Examples
This sample shows how to use the Dijkstra class
Dijkstra dijkstra = new Dijkstra(someGraph);
// Set vertex number 6 (index 5) as source vertex
dijkstra.Initialize(5);
dijkstra.Start();
See Also