Dijkstra's Algorithm in C# with Generics

I recently needed to to implement a shortest-path algorithm (to identify preferred domain controllers using site link costs)... found Dijkstra's Algorithm... found an example, then chose to modify it to support Generics...
Language:
C#
Keywords:
Code Snippet

public class Path<T>

{

    public T Source { get; set; }

    public T Destination { get; set; }

 

    /// <summary>

    /// Cost of using this path from Source to Destination

    /// </summary>

    /// <remarks>

    /// Lower costs are preferable to higher costs

    /// </remarks>

    public int Cost { get; set; }

} // class Path<T>

 

/// <summary>

/// Calculates the best route between various paths, using Dijkstra's algorithm

/// </summary>

/// <remarks>

/// Copied the algorithm's implementation from <see cref="http://www.codeproject.com/Articles/22647/Dijkstra-Shortest-Route-Calculation-Object-Oriente"/>.

/// Implementation was adjusted to support Generics, and make heavier use of LINQ

/// </remarks>

public static class Engine

{

    public static LinkedList<Path<T>> CalculateShortestPathBetween<T>(T source, T destination, IEnumerable<Path<T>> Paths)

    {

        return CalculateFrom(source, Paths)[destination];

    }

    public static Dictionary<T, LinkedList<Path<T>>> CalculateShortestFrom<T>(T source, IEnumerable<Path<T>> Paths)

    {

        return CalculateFrom(source, Paths);

    }

 

    private static Dictionary<T, LinkedList<Path<T>>> CalculateFrom<T>(T source, IEnumerable<Path<T>> Paths)

    {

        // validate the paths

        if (Paths.Any(p => p.Source.Equals(p.Destination)))

            throw new ArgumentException("No path can have the same source and destination");

 

 

 

        // keep track of the shortest paths identified thus far

        Dictionary<T, KeyValuePair<int, LinkedList<Path<T>>>> ShortestPaths = new Dictionary<T, KeyValuePair<int, LinkedList<Path<T>>>>();

        // keep track of the locations which have been completely processed

        List<T> LocationsProcessed = new List<T>();

 

        // include all possible steps, with Int.MaxValue cost

        Paths.SelectMany(p => new T[] { p.Source, p.Destination })              // union source and destinations

                .Distinct()                                                        // remove duplicates

                .ToList()                                                          // ToList exposes ForEach

                .ForEach(s => ShortestPaths.Set(s, Int32.MaxValue, null));         // add to ShortestPaths with MaxValue cost

 

        // update cost for self-to-self as 0; no path

        ShortestPaths.Set(source, 0, null);

 

        // keep this cached

        var LocationCount = ShortestPaths.Keys.Count;

 

        while (LocationsProcessed.Count < LocationCount)

        {

 

            T _locationToProcess = default(T);

 

            //Search for the nearest location that isn't handled

            foreach (T _location in ShortestPaths.OrderBy(p => p.Value.Key).Select(p => p.Key).ToList())

            {

                if (!LocationsProcessed.Contains(_location))

                {

                    if (ShortestPaths[_location].Key == Int32.MaxValue)

                        return ShortestPaths.ToDictionary(k => k.Key, v => v.Value.Value); //ShortestPaths[destination].Value;

 

                    _locationToProcess = _location;

                    break;

                }

            } // foreach

 

            var _selectedPaths = Paths.Where(p => p.Source.Equals(_locationToProcess));

            foreach (Path<T> path in _selectedPaths)

            {

                if (ShortestPaths[path.Destination].Key > path.Cost + ShortestPaths[path.Source].Key)

                {

                    ShortestPaths.Set(

                        path.Destination,

                        path.Cost + ShortestPaths[path.Source].Key,

                        ShortestPaths[path.Source].Value.Union(new Path<T>[] { path }).ToArray());

                }

            } // foreach

 

            //Add the location to the list of processed locations

            LocationsProcessed.Add(_locationToProcess);

 

        } // while

 

        return ShortestPaths.ToDictionary(k => k.Key, v => v.Value.Value);

        //return ShortestPaths[destination].Value;

    }

} // class Engine

 

 

public static class ExtensionMethods

{

    /// <summary>

    /// Adds or Updates the dictionary to include the destination and its associated cost and complete path (and param arrays make paths easier to work with)

    /// </summary>

    public static void Set<T>(this Dictionary<T, KeyValuePair<int, LinkedList<Path<T>>>> Dictionary, T destination, int Cost, params Path<T>[] paths)

    {

        var CompletePath = paths == null ? new LinkedList<Path<T>>() : new LinkedList<Path<T>>(paths);

        Dictionary[destination] = new KeyValuePair<int, LinkedList<Path<T>>>(Cost, CompletePath);

    }

} // class ExtensionMethods

Example

using Microsoft.VisualStudio.TestTools.UnitTesting;
using FluentAssertions;

[TestClass]

public class DijkstraRouteEngineTests

{

 

    [TestMethod]

    public void Calculate_A_to_D_given_AB_BC_CD__should_be__ABCD()

    {

        var Results = Engine.CalculateShortestPathBetween(

            "A",

            "D",

            new Path<string>[] {

                new Path<string>() { Source = "A", Destination = "B", Cost = 3 },

                new Path<string>() { Source = "B", Destination = "C", Cost = 3 },

                new Path<string>() { Source = "C", Destination = "D", Cost = 3 }

            });

 

        Results.Sum(r => r.Cost).Should().Be(9);

        Results.Count.Should().Be(3);

 

        Results.First().Cost.Should().Be(3);

        Results.First().Source.Should().Be("A");

        Results.First().Destination.Should().Be("B");

 

        Results.Skip(1).First().Cost.Should().Be(3);

        Results.Skip(1).First().Source.Should().Be("B");

        Results.Skip(1).First().Destination.Should().Be("C");

 

        Results.Skip(2).First().Cost.Should().Be(3);

        Results.Skip(2).First().Source.Should().Be("C");

        Results.Skip(2).First().Destination.Should().Be("D");

    }

 

    [TestMethod]

    public void Calculate_A_to_D_given_AB_BC_CD_DE__should_be__ABCD()

    {

        var Results = Engine.CalculateShortestPathBetween(

            "A",

            "D",

            new Path<string>[] {

                new Path<string>() { Source = "A", Destination = "B", Cost = 3 },

                new Path<string>() { Source = "B", Destination = "C", Cost = 3 },

                new Path<string>() { Source = "C", Destination = "D", Cost = 3 },

                new Path<string>() { Source = "D", Destination = "E", Cost = 3 }

            });

 

        Results.Sum(r => r.Cost).Should().Be(9);

        Results.Count.Should().Be(3);

 

        Results.First().Cost.Should().Be(3);

        Results.First().Source.Should().Be("A");

        Results.First().Destination.Should().Be("B");

 

        Results.Skip(1).First().Cost.Should().Be(3);

        Results.Skip(1).First().Source.Should().Be("B");

        Results.Skip(1).First().Destination.Should().Be("C");

 

        Results.Skip(2).First().Cost.Should().Be(3);

        Results.Skip(2).First().Source.Should().Be("C");

        Results.Skip(2).First().Destination.Should().Be("D");

    }

 

    [TestMethod]

    public void Calculate_A_to_D_given_AB_AC_AD_AE_BC_CD_DE__should_be__ACD()

    {

        var Results = Engine.CalculateShortestPathBetween(

            "A",

            "D",

            new Path<string>[] {

                new Path<string>() { Source = "A", Destination = "B", Cost = 3 },

                new Path<string>() { Source = "A", Destination = "C", Cost = 3 },

                new Path<string>() { Source = "A", Destination = "D", Cost = 7 }, // set this just above ABC (3+3=6)

                new Path<string>() { Source = "A", Destination = "E", Cost = 3 },

 

                new Path<string>() { Source = "B", Destination = "C", Cost = 3 },

 

                new Path<string>() { Source = "C", Destination = "D", Cost = 3 },

 

                new Path<string>() { Source = "D", Destination = "E", Cost = 3 }

            });

 

        Results.Sum(r => r.Cost).Should().Be(6);

        Results.Count.Should().Be(2);

 

        Results.First().Cost.Should().Be(3);

        Results.First().Source.Should().Be("A");

        Results.First().Destination.Should().Be("C");

 

        Results.Skip(1).First().Cost.Should().Be(3);

        Results.Skip(1).First().Source.Should().Be("C");

        Results.Skip(1).First().Destination.Should().Be("D");

    }

 

    [TestMethod]

    public void Calculate_A_to_D_given_AB_AC_AD_AE_BC_CD_DE__should_be__AD()

    {

        var Results = Engine.CalculateShortestPathBetween(

            "A",

            "D",

            new Path<string>[] {

                new Path<string>() { Source = "A", Destination = "B", Cost = 3 },

                new Path<string>() { Source = "A", Destination = "C", Cost = 3 },

                new Path<string>() { Source = "A", Destination = "D", Cost = 5 }, // set this just below ABC (3+3=6)

                new Path<string>() { Source = "A", Destination = "E", Cost = 3 },

 

                new Path<string>() { Source = "B", Destination = "C", Cost = 3 },

 

                new Path<string>() { Source = "C", Destination = "D", Cost = 3 },

 

                new Path<string>() { Source = "D", Destination = "E", Cost = 3 }

            });

 

        Results.Sum(r => r.Cost).Should().Be(5);

        Results.Count.Should().Be(1);

 

        Results.Single().Cost.Should().Be(5);

        Results.Single().Source.Should().Be("A");

        Results.Single().Destination.Should().Be("D");

    }

 

 

} // TestClass

 


Created 2012-03-05
comments powered by Disqus
Login