Mark S. Rasmussen
May 13

Through various projects, I’ve had to do some shortest-path finding in a connected graph. An efficient and straight-forward way to do this is using Dijkstra’s Algorithm. Notice that it’ll only work for graphs with non negative path weights, like 2D maps for instance. While I’ve used the algorithm on several occasions, it’s only now that I’ve rewritten it in generic form

The code is pretty much self explanatory if you keep the pseudo code implementation next to it.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Improve.Framework.Algorithms
	public class Dijkstra<TNode>
		/// <summary>
		/// Calculates the shortest route from a source node to a target node given a set of nodes and connections. Will only work for graphs with non-negative path weights.
		/// </summary>
		/// <param name="connections">All the nodes, as well as the list of their connections.</param>
		/// <param name="sourceNode">The node to start from.</param>
		/// <param name="targetNode">The node we should seek.</param>
		/// <param name="fnEquals">A function used for testing if two nodes are equal.</param>
		/// <param name="fnDistance">A function used for calculating the distance/weight between two nodes.</param>
		/// <returns>An ordered list of nodes from source->target giving the shortest path from the source to the target node. Returns null if no path is possible.</returns>
		public static List<TNode> ShortestPath(IDictionary<TNode, List<TNode>> connections, TNode sourceNode, TNode targetNode, Func<TNode, TNode, bool> fnEquals, Func<TNode, TNode, double> fnDistance)
			// Initialize values
			Dictionary<TNode, double> distance = new Dictionary<TNode, double>(); ;
			Dictionary<TNode, TNode> previous = new Dictionary<TNode, TNode>(); ;
			List<TNode> localNodes = new List<TNode>();

			// For all nodes, copy it to our local list as well as set it's distance to null as it's unknown
			foreach (TNode node in connections.Keys)
				distance.Add(node, double.PositiveInfinity);

			// We know the distance from source->source is 0 by definition
			distance[sourceNode] = 0;

			while (localNodes.Count > 0)
				// Return and remove best vertex (that is, connection with minimum distance
				TNode minNode = localNodes.OrderBy(n => distance[n]).First();

				// Loop all connected nodes
				foreach (TNode neighbor in connections[minNode])
					// The positive distance between node and it's neighbor, added to the distance of the current node
					double dist = distance[minNode] + fnDistance(minNode, neighbor);

					if (dist < distance[neighbor])
						distance[neighbor] = dist;
						previous[neighbor] = minNode;

				// If we're at the target node, break
				if (fnEquals(minNode, targetNode))

			// Construct a list containing the complete path. We'll start by looking at the previous node of the target and then making our way to the beginning.
			// We'll reverse it to get a source->target list instead of the other way around. The source node is manually added.
			List<TNode> result = new List<TNode>();
			TNode target = targetNode;
			while (previous.ContainsKey(target))
				target = previous[target];

			if (result.Count > 1)
				return result;
				return null;

Once we’ve made the list of nodes & connections, invoking the algorithm is rather simple. We just need to provide an equality function as well as a distance function:

// Run Dijkstra's algorithm
List<Point2D> result = Dijkstra<Point2D>.ShortestPath(connections, mouse, target, (p1, p2) => p1 == p2, (p1, p2) => p1.DistanceTo(p2));

Downloads - Sample code

Mark S. Rasmussen
I'm the CTO at iPaper where I cuddle with databases, mold code and maintain the overall technical & team responsibility. I'm an avid speaker at user groups & conferences. I love life, motorcycles, photography and all things technical. Say hi on Twitter, write me an email or look me up on LinkedIn.