.NET 3.5+

Dijkstra's Algorithm

by Richard Carr, published at http://www.blackwasp.co.uk/Dijkstra.aspx

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.

Graph Traversal

In mathematics, a graph is a set of interconnected nodes. These nodes often represent real-world objects. For example, a graph may be used to represent a road network, with each node corresponding to a city, town, village or other place of interest. The connections between the nodes would represent the roads that join those places. A graph's connections may be symmetric or asymmetric, also known as undirected or directed respectively. A symmetric connection can be followed in both directions, such as most roads. An asymmetric connection can only be followed in one direction, perhaps representing a one-way street.

The diagram below shows an abstract representation of a graph. In this case we have eleven lettered nodes and seventeen connections. Four of the connections are asymmetric, shown with arrowheads denoting their direction. The other connections are undirected. One node, "Z", has no connections so cannot be reached from any of the others. The numbers indicate the distances between nodes.

Graph traversal algorithms, also known as graph search algorithms, follow the connections in graphs to solve specific problems. A common problem is finding the shortest route between two nodes. This is used in network routing protocols and satellite navigation systems for road users.

Dijkstra's algorithm, named after Edsger W Dijkstra, is a graph traversal algorithm. Given a starting point within a graph, the algorithm determines the shortest route to every other connected node. Unconnected nodes, such as "Z" in the diagram, are assigned a distance of infinity.

Dijkstra's Algorithm

Dijkstra's algorithm includes five steps that calculate the distance of each node in a graph. The steps are:

1. Initialise the graph by setting the distance for every node to infinity, except for the starting node, which has a distance of zero. Mark every node in the graph as unprocessed.
2. Choose the current node. This is the unprocessed node with the smallest, non-infinite distance. If every node in the graph has been processed, or only nodes with an infinite distance remain unprocessed, the algorithm has completed. During the first iteration, the current node is the starting point.
3. Calculate the distance for all of the current node's unprocessed neighbours by adding the current distance to the length of the connection to the neighbour. For each neighbour, if the calculated distance is shorter than the neighbour's current distance, set the distance to the new value. For example, if the current node's distance from the starting point is 20 miles and the distance to a neighbour is 5 miles, the neighbour's potential distance is 25 miles. If the neighbour's distance is already less than 25 miles, it remains unchanged. If it is more than 25 miles, it's distance is overwritten and becomes 25 miles.
4. Mark the current node as processed.
5. Repeat the process from step 2.

Implementing the Algorithm

In the remainder of the article we'll implement Dijkstra's algorithm using C#. This includes some LINQ standard query operators, which require .NET 3.5. If you are using an earlier version of the framework, you can use foreach loops and conditional processing to achieve the same results. The code also includes automatically implemented properties, which will need to be expanded.

Node Class

The first class that we need represents a node in a graph. This is an internal class as we only wish it to be visible from within the project. If the algorithm and data structure classes are compiled into an assembly, this will prevent incorrect use of the data structures. The code for the Node class is shown below, with the description following:

internal class Node
{
    IList<NodeConnection> _connections;

    internal string Name { get; private set; }

    internal double DistanceFromStart { get; set; }

    internal IEnumerable<NodeConnection> Connections
    {
        get { return _connections; }
    }

    internal Node(string name)
    {
        Name = name;
        _connections = new List<NodeConnection>();
    }

    internal void AddConnection(Node targetNode, double distance, bool twoWay)
    {
        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.");

        _connections.Add(new NodeConnection(targetNode, distance));
        if (twoWay) targetNode.AddConnection(this, distance, false);
    }
}

The Node class includes three properties. The Name property allows us to provide a name for the node. This is a unique name within a graph. The DistanceFromStart property is populated by the algorithm. On completion of a calculation, this will hold the length of the shortest possible route from the starting node. The Connections property provides read-only access to the list of connections that can be followed from this node to its neighbours.

The constructor for the Node class requires that a name is provided when the object is initialised. This is stored in the Name property. The constructor also initialises the Connections property as an empty list.

The final member, "AddConnection", is used to add a connection to a neighbour, creating a NodeConnection object, which is described in the next section. The target node, distance and a flag indicating if the connection is symmetric or asymmetric must be provided. The first three lines validate the provided parameters. Next the connection is added to the node. If the twoWay flag is set, a mirror connection is created from the target node to the current object.