DijkstraAlgorithm.cs

using System;
using System.Collections.Generic;
using System.Linq;
using DataStructures.Graph;

namespace Algorithms.Graph.Dijkstra
{
    public static class DijkstraAlgorithm
    {
        /// <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>
        public static DistanceModel<T>[] GenerateShortestPath<T>(DirectedWeightedGraph<T> graph, Vertex<T> startVertex)
        {
            ValidateGraphAndStartVertex(graph, startVertex);

            var visitedVertices = new List<Vertex<T>>();

            var distanceArray = InitializeDistanceArray(graph, startVertex);

            var currentVertex = startVertex;

            var currentPath = 0d;

            while (true)
            {
                visitedVertices.Add(currentVertex);

                var neighborVertices = graph
                    .GetNeighbors(currentVertex)
                    .Where(x => x != null && !visitedVertices.Contains(x))
                    .ToList();

                foreach (var vertex in neighborVertices)
                {
                    var adjacentDistance = graph.AdjacentDistance(currentVertex, vertex!);

                    var distance = distanceArray[vertex!.Index];

                    if (distance.Distance <= currentPath + adjacentDistance)
                    {
                        continue;
                    }

                    distance.Distance = currentPath + adjacentDistance;
                    distance.PreviousVertex = currentVertex;
                }

                var minimalAdjacentVertex = GetMinimalUnvisitedAdjacentVertex(graph, currentVertex, neighborVertices);

                if (neighborVertices.Count == 0 || minimalAdjacentVertex is null)
                {
                    break;
                }

                currentPath += graph.AdjacentDistance(currentVertex, minimalAdjacentVertex);

                currentVertex = minimalAdjacentVertex;
            }

            return distanceArray;
        }

        private static DistanceModel<T>[] InitializeDistanceArray<T>(
            IDirectedWeightedGraph<T> graph,
            Vertex<T> startVertex)
        {
            var distArray = new DistanceModel<T>[graph.Count];

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

            foreach (var vertex in graph.Vertices.Where(x => x != null && !x.Equals(startVertex)))
            {
                distArray[vertex!.Index] = new DistanceModel<T>(vertex, null, double.MaxValue);
            }

            return distArray;
        }

        private static void ValidateGraphAndStartVertex<T>(DirectedWeightedGraph<T> graph, Vertex<T> startVertex)
        {
            if (graph is null)
            {
                throw new ArgumentNullException(nameof(graph));
            }

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

        private static Vertex<T>? GetMinimalUnvisitedAdjacentVertex<T>(
            IDirectedWeightedGraph<T> graph,
            Vertex<T> startVertex,
            IEnumerable<Vertex<T>?> adjacentVertices)
        {
            var minDistance = double.MaxValue;
            Vertex<T>? minVertex = default;

            foreach (var vertex in adjacentVertices)
            {
                var currentDistance = graph.AdjacentDistance(startVertex, vertex!);

                if (minDistance <= currentDistance)
                {
                    continue;
                }

                minDistance = currentDistance;
                minVertex = vertex;
            }

            return minVertex;
        }
    }
}