C# Dijkstra’s algorithm implementation

I implemented Dijkstra’s algorithm using C# for a Computer Science course. I implemented it in a generalized way, that still allows for optimization by the consuming code. I release the code under the MIT license. 

Here is the code: (it is not as long as it is well-documented)

using System; 
  using System.Diagnostics; 
  using System.Collections.Generic; 
  using System.Text; 
   
  namespace VisualIntelligentScissors 
  { 
   /// <summary> 
   /// Implements a generalized Dijkstra's algorithm to calculate 
   /// both minimum distance and minimum path. 
   /// </summary> 
   /// <remarks> 
   /// For this algorithm, all nodes should be provided, and handled 
   /// in the delegate methods, including the start and finish nodes. 
   /// </remarks> 
   public class Dijkstra 
   { 
   /// <summary> 
   /// An optional delegate that can help optimize the algorithm 
   /// by showing it a subset of nodes to consider. Very useful 
   /// for limited connectivity graphs. (like pixels on a screen!) 
   /// </summary> 
   /// <param name="startingNode"> 
   /// The node that is being traveled away FROM. 
   /// </param> 
   /// <returns> 
   /// An array of nodes that might be reached from the  
   /// <paramref name="startingNode"/>. 
   /// </returns> 
   public delegate IEnumerable<int> NearbyNodesHint(int startingNode); 
   /// <summary> 
   /// Determines the cost of moving from a given node to another given node. 
   /// </summary> 
   /// <param name="start"> 
   /// The node being moved away from. 
   /// </param> 
   /// <param name="finish"> 
   /// The node that may be moved to. 
   /// </param> 
   /// <returns> 
   /// The cost of the transition from <paramref name="start"/> to 
   /// <paramref name="finish"/>, or <see cref="Int32.MaxValue"/> 
   /// if the transition is impossible (i.e. there is no edge between  
   /// the two nodes). 
   /// </returns> 
   public delegate int InternodeTraversalCost(int start, int finish); 
   
   /// <summary> 
   /// Creates an instance of the <see cref="Dijkstra"/> class. 
   /// </summary> 
   /// <param name="totalNodeCount"> 
   /// The total number of nodes in the graph. 
   /// </param> 
   /// <param name="traversalCost"> 
   /// The delegate that can provide the cost of a transition between 
   /// any two nodes. 
   /// </param> 
   /// <param name="hint"> 
   /// An optional delegate that can provide a small subset of nodes 
   /// that a given node may be connected to. 
   /// </param> 
   public Dijkstra(int totalNodeCount, InternodeTraversalCost traversalCost, NearbyNodesHint hint) 
   { 
   if (totalNodeCount < 3) throw new ArgumentOutOfRangeException("totalNodeCount", totalNodeCount, "Expected a minimum of 3."); 
   if (traversalCost == null) throw new ArgumentNullException("traversalCost"); 
   Hint = hint; 
   TraversalCost = traversalCost; 
   TotalNodeCount = totalNodeCount; 
   } 
   
   protected readonly NearbyNodesHint Hint; 
   protected readonly InternodeTraversalCost TraversalCost; 
   protected readonly int TotalNodeCount; 
   
   /// <summary> 
   /// The composite product of a Dijkstra algorithm. 
   /// </summary> 
   public struct Results 
   { 
   /// <summary> 
   /// Prepares a Dijkstra results package. 
   /// </summary> 
   /// <param name="minimumPath"> 
   /// The minimum path array, where each array element index corresponds  
   /// to a node designation, and the array element value is a pointer to 
   /// the node that should be used to travel to this one. 
   /// </param> 
   /// <param name="minimumDistance"> 
   /// The minimum distance from the starting node to the given node. 
   /// </param> 
   public Results(int[] minimumPath, int[] minimumDistance) 
   { 
   MinimumDistance = minimumDistance; 
   MinimumPath = minimumPath; 
   } 
   
   /// <summary> 
   /// The minimum path array, where each array element index corresponds  
   /// to a node designation, and the array element value is a pointer to 
   /// the node that should be used to travel to this one. 
   /// </summary> 
   public readonly int[] MinimumPath; 
   /// <summary> 
   /// The minimum distance from the starting node to the given node. 
   /// </summary> 
   public readonly int[] MinimumDistance; 
   } 
   
   /// <summary> 
   /// Performs the Dijkstra algorithm on the data provided when the  
   /// <see cref="Dijkstra"/> object was instantiated. 
   /// </summary> 
   /// <param name="start"> 
   /// The node to use as a starting location. 
   /// </param> 
   /// <returns> 
   /// A struct containing both the minimum distance and minimum path 
   /// to every node from the given <paramref name="start"/> node. 
   /// </returns> 
   public virtual Results Perform(int start) 
   { 
   // Initialize the distance to every node from the starting node. 
   int[] d = GetStartingTraversalCost(start); 
   // Initialize best path to every node as from the starting node. 
   int[] p = GetStartingBestPath(start); 
   ICollection<int> c = GetChoices(); 
   
   c.Remove(start); // take starting node out of the list of choices 
   
   //Debug.WriteLine("Step v C D P"); 
   //Debug.WriteLine(string.Format("init - {{{0}}} [{1}] [{2}]", 
   // ArrayToString<int>(",", c), ArrayToString<int>(",", d), ArrayToString<int>(",", p))); 
   //int step = 0; 
   
   // begin greedy loop 
   while (c.Count > 1) 
   { 
   // Find element v in c, that minimizes d[v] 
   int v = FindMinimizingDinC(d, c); 
   c.Remove(v); // remove v from the list of future solutions 
   // Consider all unselected nodes and consider their cost from v. 
   foreach (int w in (Hint != null ? Hint(v) : c)) 
   { 
   if (!c.Contains(w)) continue; // discard pixels not in c 
   // At this point, relative(Index) points to a candidate pixel,  
   // that has not yet been selected, and lies within our area of interest. 
   // Consider whether it is now within closer reach. 
   int cost = TraversalCost(v, w); 
   if (cost < int.MaxValue && d[v] + cost < d[w]) // don't let wrap-around negatives slip by 
   { 
   // We have found a better way to get at relative 
   d[w] = d[v] + cost; // record new distance 
   // Record how we came to this new pixel 
   p[w] = v; 
   } 
   } 
   //Debug.WriteLine(string.Format("{4} {3} {{{0}}} [{1}] [{2}]", 
   // ArrayToString<int>(",", c), ArrayToString<int>(",", d), ArrayToString<int>(",", p), v + 1, ++step)); 
   } 
   
   return new Results(p, d); 
   } 
   
   /// <summary> 
   /// Uses the Dijkstra algorithhm to find the minimum path 
   /// from one node to another. 
   /// </summary> 
   /// <param name="start"> 
   /// The node to use as a starting location. 
   /// </param> 
   /// <param name="finish"> 
   /// The node to use as a finishing location. 
   /// </param> 
   /// <returns> 
   /// A struct containing both the minimum distance and minimum path 
   /// to every node from the given <paramref name="start"/> node. 
   /// </returns> 
   public virtual int[] GetMinimumPath(int start, int finish) 
   { 
   Results results = Perform(start); 
   return GetMinimumPath(start, finish, results.MinimumPath); 
   } 
   
   /// <summary> 
   /// Finds an array of nodes that provide the shortest path 
   /// from one given node to another. 
   /// </summary> 
   /// <param name="start"> 
   /// The starting node. 
   /// </param> 
   /// <param name="finish"> 
   /// The finishing node. 
   /// </param> 
   /// <param name="shortestPath"> 
   /// The P array of the completed algorithm. 
   /// </param> 
   /// <returns> 
   /// The list of nodes that provide the one step at a time path  
   /// from <paramref name="start"/> to <paramref name="finish"/> nodes. 
   /// </returns> 
   protected virtual int[] GetMinimumPath(int start, int finish, int[] shortestPath) 
   { 
   Stack<int> path = new Stack<int>(); 
   do 
   { 
   path.Push(finish); 
   finish = shortestPath[finish]; // step back one step toward the start point 
   } 
   while (finish != start); 
   return path.ToArray(); 
   } 
   
   /// <summary> 
   /// Initializes the P array for the algorithm. 
   /// </summary> 
   /// <param name="startingNode"> 
   /// The node that has been designated the starting node for the entire algorithm. 
   /// </param> 
   /// <returns> 
   /// The new P array. 
   /// </returns> 
   /// <remarks> 
   /// A fresh P array will set every single node's source node to be  
   /// the starting node, including the starting node itself. 
   /// </remarks> 
   protected virtual int[] GetStartingBestPath(int startingNode) 
   { 
   int[] p = new int[TotalNodeCount]; 
   for (int i = 0; i < p.Length; i++) 
   p[i] = startingNode; 
   return p; 
   } 
   
   /// <summary> 
   /// Finds the yet-unconsidered node that has the least cost to reach. 
   /// </summary> 
   /// <param name="d"> 
   /// The cost of reaching any node. 
   /// </param> 
   /// <param name="c"> 
   /// The nodes that are still available for picking. 
   /// </param> 
   /// <returns> 
   /// The node that is closest (has the shortest special path). 
   /// </returns> 
   protected virtual int FindMinimizingDinC(int[] d, ICollection<int> c) 
   { 
   int bestIndex = -1; 
   foreach (int ci in c) 
   if (bestIndex == -1 || d[ci] < d[bestIndex]) 
   bestIndex = ci; 
   return bestIndex; 
   } 
   
   /// <summary> 
   /// Initializes an collection of all nodes not yet considered. 
   /// </summary> 
   /// <returns> 
   /// The initialized collection. 
   /// </returns> 
   protected virtual ICollection<int> GetChoices() 
   { 
   ICollection<int> choices = new List<int>(TotalNodeCount); 
   for (int i = 0; i < TotalNodeCount; i++) 
   choices.Add(i); 
   return choices; 
   } 
   
   /// <summary> 
   /// Initializes the D array for the start of the algorithm. 
   /// </summary> 
   /// <param name="start"> 
   /// The starting node. 
   /// </param> 
   /// <returns> 
   /// The contents of the new D array. 
   /// </returns> 
   /// <remarks> 
   /// The traversal cost for every node will be set to impossible 
   /// (int.MaxValue) unless a connecting edge is found between the 
   /// <paramref name="start"/>ing node and the node in question. 
   /// </remarks> 
   protected virtual int[] GetStartingTraversalCost(int start) 
   { 
   int[] subset = new int[TotalNodeCount]; 
   for (int i = 0; i < subset.Length; i++) 
   subset[i] = int.MaxValue; // all are unreachable 
   subset[start] = 0; // zero cost from start to start 
   foreach (int nearby in Hint(start)) 
   subset[nearby] = TraversalCost(start, nearby); 
   return subset; 
   } 
   
   /// <summary> 
   /// Joins the elements of an array into a string, using 
   /// a given separator. 
   /// </summary> 
   /// <typeparam name="T">The type of element in the array.</typeparam> 
   /// <param name="separator">The seperator to insert between each element.</param> 
   /// <param name="array">The array.</param> 
   /// <returns>The resulting string.</returns> 
   /// <remarks> 
   /// This is very much like <see cref="string.Join"/>, except 
   /// that it works on arrays of non-strings. 
   /// </remarks> 
   protected string ArrayToString<T>(string separator, IEnumerable<int> array) 
   { 
   StringBuilder sb = new StringBuilder(); 
   foreach (int t in array) 
   sb.AppendFormat("{0}{1}", t < int.MaxValue ? t + 1 : t, separator); 
   sb.Length -= separator.Length; 
   return sb.ToString(); 
   } 
   
   } 
  } 
  

The course I wrote this class for wanted me to add this algorithm to a simple graphics program that would "cut out" shapes using the shortest cost path. Here are the intelligent scissors that I wrote:

using System; 
  using System.Diagnostics; 
  using System.Collections.Generic; 
  using System.Drawing; 
   
  namespace VisualIntelligentScissors 
  { 
   public class DijkstraScissors : Scissors 
   { 
   public DijkstraScissors() { } 
   public DijkstraScissors(GrayBitmap image, Bitmap overlay) : base(image, overlay) { } 
   
   int[,] traversalCost; 
   Rectangle relevantRegion; 
   protected int relevantPixelsCount 
   { 
   get { return relevantRegion.Width * relevantRegion.Height; } 
   } 
   
   public override void Trace(IList<Point> points, Pen pen) 
   { 
   if (Image == null) throw new InvalidOperationException("Set Image property first."); 
   
   using (Graphics g = Graphics.FromImage(Overlay)) 
   { 
   for (int i = 0; i < points.Count; i++) 
   { 
   // Our segment travels from start to finish 
   Point start = points[i]; 
   Point finish = points[(i + 1) % points.Count]; 
   
   // Consider only some nearby region, to speed up processing. 
   relevantRegion = GetRelevantRegion(start, finish); 
   // Find the cost of moving to any pixel. 
   traversalCost = GetTraversalCost(); 
   
   // Calculate what the array indexes are for the two known pixels 
   int startIndex = GetArrayIndex(start); 
   int finishIndex = GetArrayIndex(finish); 
   
   Dijkstra dijkstra = new Dijkstra( 
   relevantPixelsCount, 
   new Dijkstra.InternodeTraversalCost(getInternodeTraversalCost), 
   new Dijkstra.NearbyNodesHint(nearbyNodesHint) 
   ); 
   int[] minimumPath = dijkstra.GetMinimumPath(startIndex, finishIndex); 
   
   // By now we should have found the best path between start and finish, 
   // considering all within the designated relevantRegion. 
   drawMinimumPath(minimumPath, pen.Color); 
   
   //g.DrawRectangle(Pens.Green, relevantRegion); 
   Program.MainForm.RefreshImage(); 
   System.Windows.Forms.Application.DoEvents(); 
   } 
   } 
   } 
   
   private void drawMinimumPath(int[] path, Color color) 
   { 
   // Show user goal point. 
   Point finish = GetPointFromArrayIndex(path[path.Length-1]); 
   Overlay.SetPixel(finish.X, finish.Y, color); 
   
   // Draw entire path 
   foreach (int index in path) 
   { 
   Point point = GetPointFromArrayIndex(index); 
   Overlay.SetPixel(point.X, point.Y, color); 
   //Program.MainForm.RefreshImage(); 
   //System.Windows.Forms.Application.DoEvents(); 
   } 
   } 
   
   private Rectangle GetRelevantRegion(Point start, Point finish) 
   { 
   const int minimumSpace = 5; 
   const float expansion = 0.01F; 
   
   Rectangle rect = Rectangle.FromLTRB( 
   Math.Min(start.X, finish.X), 
   Math.Min(start.Y, finish.Y), 
   Math.Max(start.X, finish.X), 
   Math.Max(start.Y, finish.Y) 
   ); 
   rect.Inflate(Math.Max((int)(rect.Width * expansion), minimumSpace), 
   Math.Max((int)(rect.Height * expansion), minimumSpace)); 
   // Make sure our relevant region stays within the bounds or calculating a gradient. 
   rect.Intersect(Rectangle.FromLTRB(1, 1, Image.Bitmap.Width - 1, Image.Bitmap.Height - 1)); 
   Debug.Assert(rect.Contains(start), "Relevant region does not contain start point."); 
   Debug.Assert(rect.Contains(finish), "Relevant region does not contain finish point."); 
   return rect; 
   } 
   
   private int GetArrayIndex(Point point) 
   { 
   if (!relevantRegion.Contains(point)) return -1; 
   Point offset = point; 
   offset.Offset(-relevantRegion.X, -relevantRegion.Y); // remove effect of offset region 
   return offset.Y * relevantRegion.Width + offset.X; 
   } 
   private Point GetPointFromArrayIndex(int index) 
   { 
   Point point = new Point(index % relevantRegion.Width, index / relevantRegion.Width); 
   point.Offset(relevantRegion.Location); 
   return point; 
   } 
   
   private int[] GetPixelWeights() 
   { 
   int[] weights = new int[relevantPixelsCount]; 
   for (int i = 0; i < weights.Length; i++) 
   weights[i] = GetPixelWeight(GetPointFromArrayIndex(i)); 
   return weights; 
   } 
   const int maximumNearbyPositions = 4; 
   enum NearbyPosition : int 
   { 
   Above = 0, 
   Left, 
   Right, 
   Below 
   } 
   private int GetNearbyPixel(int origin, NearbyPosition relative) 
   { 
   return GetArrayIndex(GetNearbyPixel(GetPointFromArrayIndex(origin), relative)); 
   } 
   private Point GetNearbyPixel(Point origin, NearbyPosition relative) 
   { 
   Point offset = origin; 
   switch (relative) 
   { 
   case NearbyPosition.Above: 
   offset.Offset(0, -1); 
   break; 
   case NearbyPosition.Below: 
   offset.Offset(0, 1); 
   break; 
   case NearbyPosition.Left: 
   offset.Offset(-1, 0); 
   break; 
   case NearbyPosition.Right: 
   offset.Offset(1, 0); 
   break; 
   default: 
   throw new NotSupportedException(); 
   } 
   return offset; 
   } 
   private int GetRelativePosition(int start, int finish) 
   { 
   Point startPoint = GetPointFromArrayIndex(start); 
   Point finishPoint = GetPointFromArrayIndex(finish); 
   foreach (NearbyPosition position in Enum.GetValues(typeof(NearbyPosition))) 
   if (GetNearbyPixel(start, position) == finish) 
   return (int)position; 
   return -1; 
   } 
   private int[,] GetTraversalCost() 
   { 
   int[] weights = GetPixelWeights(); 
   int[,] cost = new int[relevantPixelsCount, maximumNearbyPositions]; 
   for (int i = 0; i < weights.Length; i++) 
   { 
   Point origin = GetPointFromArrayIndex(i); 
   foreach (NearbyPosition relativePosition in Enum.GetValues(typeof(NearbyPosition))) 
   { 
   Point relative = GetNearbyPixel(origin, relativePosition); 
   if (relevantRegion.Contains(relative)) 
   { 
   int j = GetArrayIndex(relative); 
   cost[i, (int)relativePosition] = weights[j]; 
   } 
   } 
   } 
   return cost; 
   } 
   
   private IEnumerable<int> nearbyNodesHint(int startingNode) 
   { 
   List<int> nearbyNodes = new List<int>(maximumNearbyPositions); 
   foreach (NearbyPosition position in Enum.GetValues(typeof(NearbyPosition))) 
   nearbyNodes.Add(GetNearbyPixel(startingNode, position)); 
   return nearbyNodes; 
   } 
   private int getInternodeTraversalCost(int start, int finish) 
   { 
   int relativePosition = GetRelativePosition(start, finish); 
   if (relativePosition < 0) return int.MaxValue; 
   return traversalCost[start, relativePosition]; 
   } 
   } 
  }

There are other dependencies not included here (such as the Scissors base class).  My purpose in this blog is to publish a generalized Dijkstra algorithm and give an example of how to use it.  If you would like the full source code, contact me to get me to email the code to you.  My BYU professor doesn’t want BYU CS students getting the entire solution to their assigned projects.

[Updated 12/14/06]: The full source code is useful if you need a sample of how to apply the above algorithm in your own app.  Due to large demand for the source code and my limited resources to manually send it out (I can’t just link to it here since my BYU professor doesn’t want BYU CS students getting the entire solution to their assigned projects) I now charge a small processing fee of $5 to send you the source code.  If you would like the full source code, PayPal $5 to me and include your email address to get me to email the source code to you.  [Updated 8/30/07]: Do not use your credit card as the source of the $5 to send me PayPal money as PayPal will happily take half of the money for itself.  If you use your credit card, I’ll reject payment and ask you to transfer money to your PayPal account from your bank account first.

You can also download the compiled assembly for free:

[Updated 3/16/07]: Comments now closed, due to people not reading the previous paragraph and still posting comments asking for the full source.