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) and I found Dijkstra's Algorithm

Path class

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DijkstraAlgorithm {
   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>
      /// 
      /// Lower costs are preferable to higher costs
      /// </remarks>
      public int Cost { get; set; }
   }
}

ExtensionMethods class

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DijkstraAlgorithm {
   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);
      }
   }
}

Engine class

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DijkstraAlgorithm {
   /// <summary>
   /// Calculates the best route between various paths, using Dijkstra's algorithm
   /// </summary>
   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());
               }
            }

            //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;
      }
   }
}

Test

using System.Linq;
using DijkstraAlgorithm;
using FluentAssertions;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace UnitTestProject1 {
   [TestClass]
   public class UnitTest1 {
      [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");
      }
   }
}

You can find the code on GitHub.

Happy coding!

Advertsing

125X125_06

TagCloud

MonthList

CommentList