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!
