DijkstraAlgorithm.cs

usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingDataStructures.Graph;

namespaceAlgorithms.Graph.Dijkstra;

publicstaticclassDijkstraAlgorithm
{
/// <summary>
/// Implementation of the Dijkstra shortest path algorithm for cyclic graphs.
/// https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm.
/// </summary>
/// <param name="graph">Graph instance.</param>
/// <param name="startVertex">Starting vertex instance.</param>
/// <typeparam name="T">Generic Parameter.</typeparam>
/// <returns>List of distances from current vertex to all other vertices.</returns>
/// <exception cref="InvalidOperationException">Exception thrown in case when graph is null or start
/// vertex does not belong to graph instance.</exception>
publicstaticDistanceModel<T>[]GenerateShortestPath<T>(DirectedWeightedGraph<T>graph,Vertex<T>startVertex)
{
ValidateGraphAndStartVertex(graph,startVertex);

varvisitedVertices=newList<Vertex<T>>();

vardistanceArray=InitializeDistanceArray(graph,startVertex);

vardistanceRecord=newPriorityQueue<DistanceModel<T>,double>();

distanceRecord.Enqueue(distanceArray[0],distanceArray[0].Distance);

while(visitedVertices.Count!=distanceArray.Length&&distanceRecord.Count!=0)
{
while(visitedVertices.Contains(distanceRecord.Peek().Vertex!))
{
distanceRecord.Dequeue();
}

varminDistance=distanceRecord.Dequeue();

varcurrentPath=minDistance.Distance;

visitedVertices.Add(minDistance.Vertex!);

varneighborVertices=graph
.GetNeighbors(minDistance.Vertex!)
.Where(x =>x!=null&&!visitedVertices.Contains(x))
.ToList();

foreach(varvertexinneighborVertices)
{
varadjacentDistance=graph.AdjacentDistance(minDistance.Vertex!,vertex!);

vardistance=distanceArray[vertex!.Index];

varfullDistance=currentPath+adjacentDistance;

if(distance.Distance>fullDistance)
{
distance.Distance=fullDistance;
distance.PreviousVertex=minDistance.Vertex;
distanceRecord.Enqueue(distance,fullDistance);
}
}
}

returndistanceArray;
}

privatestaticDistanceModel<T>[]InitializeDistanceArray<T>(
IDirectedWeightedGraph<T>graph,
Vertex<T>startVertex)
{
vardistArray=newDistanceModel<T>[graph.Count];

distArray[startVertex.Index]=newDistanceModel<T>(startVertex,startVertex,0);

foreach(varvertexingraph.Vertices.Where(x =>x!=null&&!x.Equals(startVertex)))
{
distArray[vertex!.Index]=newDistanceModel<T>(vertex,null,double.MaxValue);
}

returndistArray;
}

privatestaticvoidValidateGraphAndStartVertex<T>(DirectedWeightedGraph<T>graph,Vertex<T>startVertex)
{
if(graphisnull)
{
thrownewArgumentNullException(nameof(graph));
}

if(startVertex.Graph!=null&&!startVertex.Graph.Equals(graph))
{
thrownewArgumentNullException(nameof(graph));
}
}
}