BlackWaspTM

This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Algorithms and Data Structures
.NET 3.5+

Dijkstra's Algorithm

Graph traversal algorithms are used to process a graph of interconnected nodes, visiting each node by following a set behaviour. Dijkstra's algorithm is such an algorithm. It determines the shortest path from a start point to all other nodes in a graph.

NodeConnection Class

The NodeConnection class represents a one-way connection to a node. When you create a two-way connection, two NodeConnection objects are generated. The code for the class is shown below:

internal class NodeConnection
{
    internal Node Target { get; private set; }
    internal double Distance { get; private set; }

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

This class holds two properties for the target node and the distance between the pair of nodes. The source node is not included as NodeConnection objects are always used in the context of the source Node object.

Graph Class

The final data structure class is Graph. Objects of this type hold entire graphs containing nodes and connections.

public class Graph
{
    internal IDictionary<string, Node> Nodes { get; private set; }

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

    public void AddNode(string name)
    {
        var node = new Node(name);
        Nodes.Add(name, node);
    }

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

The Graph class includes a single internal member, which holds a dictionary of nodes. Nodes are added using the AddNode method. This creates a new node and adds it to the dictionary, using the name as the key. If you attempt to add two nodes with the same name, an exception will be thrown. The AddConnection method is used to create connections between neighbours.

DistanceCalculator Class

With the data structures in place we can now implement the algorithm. To begin, create a class named "DistanceCalculator" and add the method declaration shown below. The method has parameters to receive a graph and a starting node. It returns a dictionary containing the names of all of the nodes in the graph and their total distances from the starting point.

public class DistanceCalculator
{
    public IDictionary<string, double> CalculateDistances(Graph graph, string startingNode)
    {
    }
}

Before starting the calculations, we will check that the node name provided is actually within the graph and throw an exception if it is not.

if (!graph.Nodes.Any(n => n.Key == startingNode))
    throw new ArgumentException("Starting node must be in graph.");

To complete the method we'll break the algorithm into three phases and create a further, private method for each. The first phase will initialise the graph as per step 1 in the algorithm description. The second method will traverse the graph and calculate the distances for each node. The final step will create and return the resultant dictionary of nodes and distances.

InitialiseGraph(graph, startingNode);
ProcessGraph(graph, startingNode);
return ExtractDistances(graph);

The initialisation step sets all of the node distances except the starting point to infinity. The starting node has a distance of zero.

private void InitialiseGraph(Graph graph, string startingNode)
{
    foreach (Node node in graph.Nodes.Values)
        node.DistanceFromStart = double.PositiveInfinity;
    graph.Nodes[startingNode].DistanceFromStart = 0;
}

The ProcessGraph method contains the code that traverses the graph until all nodes are processed or only unreachable nodes remain. Rather than flagging each node as processed or unprocessed, a "queue" of nodes to be processed is generated. Initially this contains all of the nodes. As nodes are processed they are removed from the collection.

The while loop controls the processing of the node queue. In each iteration the next node to process is obtained by retrieving the first node from the queue when sorted by distance. The call to FirstOrDefault includes a filtering lambda expression that excludes nodes with an infinite distance. If there are no non-infinite distance nodes remaining, FirstOrDefault returns null and the loop exits. If a matching node is present, this becomes the current node and is processed using the ProcessNode method.

private void ProcessGraph(Graph graph, string startingNode)
{
    bool finished = false;
    var queue = graph.Nodes.Values.ToList();
    while (!finished)
    {
        Node nextNode = queue.OrderBy(n => n.DistanceFromStart).FirstOrDefault(
            n => !double.IsPositiveInfinity(n.DistanceFromStart));
        if (nextNode != null)
        {
            ProcessNode(nextNode, queue);
            queue.Remove(nextNode);
        }
        else
        {
            finished = true;
        }
    }
}

The next method is ProcessNode, which is responsible for calculating the distances for all neighbours of the current node. To do so it first obtains the list of connections from the current node to all unprocessed neighbouring nodes. We don't need processed neighbours as these already hold the correct shortest route distance.

The total distance to each of the neighbouring nodes is calculated by adding the connection distance to the DistanceFromStart value of the current node. If the calculated distance is shorter than the neighbours current DistanceFromStart, the property value is set to the new calculated value.

private void ProcessNode(Node node, List<Node> queue)
{
    var connections = node.Connections.Where(c => queue.Contains(c.Target));
    foreach (var connection in connections)
    {
        double distance = node.DistanceFromStart + connection.Distance;
        if (distance < connection.Target.DistanceFromStart)
            connection.Target.DistanceFromStart = distance;
    }
}

The final method generates the results in a dictionary that can be used by the calling method without knowledge of the internal classes. It uses the ToDictionary standard query operator to generate a dictionary where the keys are the names of the nodes and the values are the distances.

private IDictionary<string, double> ExtractDistances(Graph graph)
{
    return graph.Nodes.ToDictionary(n => n.Key, n => n.Value.DistanceFromStart);
}
29 May 2011