DijkstrasShortestPath.cs

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

//
// Dijkstra's Algorithm - Is a graph traversal algorithm that determines the  shortest
// route from a starting node to every other connected node.  Unconnected nodes have a 
// distance of infinity.
//
// TODO: The unvisited nodes should be stored in a minheap.

namespace DijkstrasShortestPath
{
    /// <summary>
    /// Represents a single one-way connection to a node.
    /// For symmetric/undirected connections two NodeConnection objects will be created.
    /// </summary>
    internal class NodeConnection
    {
        internal Node Target {get; private set;}
        internal double Distance {get; private set;}

        internal NodeConnection(Node target, double distance)
        {
            this.Target = target;
            this.Distance = distance;
        }
    }

    /// <summary>
    /// Represents a single node on the graph.
    /// </summary>
    internal class Node
    {
        private readonly List<NodeConnection> connections = new List<NodeConnection>();

        /// <summary>
        /// Name of node in graph.
        /// </summary>
        internal string Name { get; private set; }

        /// <summary>
        /// The shortest possible route from the starting node that was found.
        /// </summary>
        internal double DistanceFromStart { get; set; }

        internal IReadOnlyList<NodeConnection> Connections
        {
            get { return connections.AsReadOnly();  }
        }

        internal Node(string name)
        {
            this.Name = name;
        }

        internal void AddConnection(Node targetNode, double distance, bool isSymmetric)
        {
            // preconditions
            if (targetNode == null) throw new ArgumentNullException("targetNode");
            if (targetNode == this) throw new ArgumentException("Node may not connect to itself.");
            if (distance <= 0) throw new ArgumentException("Distance must be positive.");

            this.connections.Add(new NodeConnection(targetNode, distance));

            // If symmetric/undirected Create mirroring connection from target node to current node.
            if (isSymmetric) targetNode.AddConnection(this, distance, false);
        }

    }

    /// <summary>
    /// Represents the entire graph containing all the nodes and their connections.
    /// </summary>
    public class Graph
    {
        internal IDictionary<string, Node> Nodes { get; private set; }

        public Graph()
        {
            this.Nodes = new Dictionary<string, Node>();
        }

        /// <summary>
        /// Adds a unique node to the graph.
        /// </summary>
        public void AddNode(string name)
        {
            var node = new Node(name);
            Nodes.Add(name, node);
        }

        public void AddConnection(string fromNode, string toNode, int distance, bool isSymmetric)
        {
            Nodes[fromNode].AddConnection(Nodes[toNode], distance, isSymmetric);
        }
    }

    /// <summary>
    /// Finds the shortest route between two nodes.
    /// Note: Unconnected nodes are assigned a distance of infinity.
    /// </summary>
    public class ShortestPathCalculator
    {
        public IDictionary<string ,double> Calculate(Graph graph, string startingNode)
        {
            // Preconditions
            if (!graph.Nodes.ContainsKey(startingNode))
                throw new ArgumentException("Starting node must exist in graph.");

            InitialiseGraph(graph, startingNode);
            ProcessDistancesFromStart(graph, startingNode);
            return ExtractDistances(graph);
        }

        /// <summary>
        /// Initialize the graph by setting the distance of every node to infinity, except for the
        /// starting node which has a distance of zero.  Mark every node in the graph as unprocessed.
        /// </summary>
        private void InitialiseGraph(Graph graph, string startingNode)
        {
            foreach (var node in graph.Nodes.Values)
                node.DistanceFromStart = double.PositiveInfinity;

            graph.Nodes[startingNode].DistanceFromStart = 0;
        }

        /// <summary>
        /// Traverse graph and calculate the distance from the start for each node.
        /// </summary>
        private void ProcessDistancesFromStart(Graph graph, string startingNode)
        {
            var unvisitedNodes = graph.Nodes.Values.ToList();
            while(true)
            {
				// TODO: Change this to use a minheap for better performance.
				
                // Choose the unvisted node with the shortest distance to the starting node.
                var nextNode = unvisitedNodes
                    .OrderBy(x => x.DistanceFromStart)
                    .FirstOrDefault(x => !double.IsPositiveInfinity(x.DistanceFromStart));

                // Stop when all connected nodes have been visited.
                if (nextNode == null)
                    break;

                ProcessNeighbors(nextNode, unvisitedNodes);
				
                unvisitedNodes.Remove(nextNode);
            }
        }

        /// <summary>
        /// Calculates the distance to the starting node for all the neighbors of the current node.
		/// If the neighbor already has a distance assigned take the shorter of the two distances.
        /// </summary>
        private void ProcessNeighbors(Node nodeToVisit, List<Node> unvisitedNodes)
        {
            Debug.Assert(nodeToVisit.DistanceFromStart != double.PositiveInfinity, "Expected processed node with a distance from the start.");

            // Get all neighbors of this node.
            var connections = nodeToVisit.Connections.Where(c => unvisitedNodes.Contains(c.Target));

            foreach (var connection in connections)
            {
                // add the connection distance to the distance from start of the current node.
                var distance = nodeToVisit.DistanceFromStart + connection.Distance;

                // If distance is shorter then than the neighbors current distance from start
                // update it with the shorter value.
                if (distance < connection.Target.DistanceFromStart)
                    connection.Target.DistanceFromStart = distance;
            }
        }

        /// <summary>
        /// Create dictionary of nodes and their distances from the starting node.
        /// </summary>
        private IDictionary<string, double> ExtractDistances(Graph graph)
        {
            return graph.Nodes.ToDictionary(n => n.Key, n => n.Value.DistanceFromStart);
        }
    }

    public static class Program
    {
        public static void Main()
        {
            Graph graph = new Graph();

            //Nodes
            graph.AddNode("A");
            graph.AddNode("B");
            graph.AddNode("C");
            graph.AddNode("D");
            graph.AddNode("E");
            graph.AddNode("F");
            graph.AddNode("G");
            graph.AddNode("H");
            graph.AddNode("I");
            graph.AddNode("J");
            graph.AddNode("Z");

            //Connections
            graph.AddConnection("A", "B", 14, true);
            graph.AddConnection("A", "C", 10, true);
            graph.AddConnection("A", "D", 14, true);
            graph.AddConnection("A", "E", 21, true);
            graph.AddConnection("B", "C", 9, true);
            graph.AddConnection("B", "E", 10, true);
            graph.AddConnection("B", "F", 14, true);
            graph.AddConnection("C", "D", 9, false);
            graph.AddConnection("D", "G", 10, false);
            graph.AddConnection("E", "H", 11, true);
            graph.AddConnection("F", "C", 10, false);
            graph.AddConnection("F", "H", 10, true);
            graph.AddConnection("F", "I", 9, true);
            graph.AddConnection("G", "F", 8, false);
            graph.AddConnection("G", "I", 9, true);
            graph.AddConnection("H", "J", 9, true);
            graph.AddConnection("I", "J", 10, true);

            var calculator = new ShortestPathCalculator();
            var start = "G";
            var distances = calculator.Calculate(graph, start);

            foreach (var d in distances) { Console.WriteLine("{0}, {1}", d.Key, d.Value); }

            Console.WriteLine("Press [Enter] to exit.");
            Console.ReadLine();
        }
    }
}