This is intended as a multipart series about shortest path finding and routing algorithms. My plan is to start with simple routing algorithms and to gradually cover more complex algorithms. The rough outline is:

  1. exhaustive search strategies,
  2. weighted graphs,
  3. Dijkstra's algorithm,
  4. A* search algorithm and heuristics, and
  5. shortest path finding in time dependant networks.

I will implement all algorithms and data structures for this series in C#.

Networks

Let's start with a simple network with five nodes:

A graph with five nodes.

From the picture we can intuitively deduce that every node can be reached from every other node. For example Node A is connected to Node B and Node C. Node B is connected to Node C, and Node D. Node C is connected to Node D and Node E; thus by going through Node B or Node C Node A is connected to all nodes in the graph.

On the other hand it is not always the case that all nodes can be reached from any node. In the follwoing graph not all nodes can be reached from Node A.

A graph with five nodes in two components.

As graphs increase in size, it becomes harder to determine if two nodes are connected. Before diving into the algorithms, let's explore how we can represent these graphs in code.

We can represent a graph as a map that maps the node's name to a list of adjacent nodes. In C# we can accomplish this using a Dictionary<string, List<string>> instance. This way the first graph would be represented like this:

var nodeA = "Node A";
var nodeB = "Node B";
var nodeC = "Node C";
var nodeD = "Node D";
var nodeE = "Node E";

var graph = new Dictionary<string, List<string>>()
{
    { nodeA, [nodeB, nodeC] },
    { nodeB, [nodeA, nodeC] },
    { nodeC, [nodeA, nodeB, nodeD, nodeE] },
    { nodeD, [nodeB, nodeC, nodeE] },
    { nodeE, [nodeC, nodeD] }
};

In general there are three strategies how to search a graph: breath-first, depth-frist and iterative deepening.

Starting from a given initial node we we first check all neighbors of a node. Once we searched all the neighbors we check all the neighbors of the neighbors and so on until we find the destination node or have checked all nodes.

Classical breath frist search using a Queue looks like this

public static string? FindDestinationByBreathFirstSearch(Dictionary<string, List<string>> graph, string origin, string destination)
{
    var nodeQueue = new Queue<string>();
    
    nodeQueue.Enqueue(origin);

    while (nodeQueue.TryDequeue(out var node))
    {
        foreach (var neighbor in graph.GetValueOrDefault(node, []))
        {
            if (neighbor == destination)
            {
                return neighbor;
            }

            nodeQueue.Enqueue(neighbor);
        }
    }

    return null;
}

Starting from origin this algorithm will follow a path until destination if it exists and return the destination node or return null if there is no path. What is missing is the path itself.

public static string[]? FindPathToDestinationByBreathFirstSearch(Dictionary<string, List<string>> graph, string origin, string destination)
{
    var nodeQueue = new Queue<string[]>();
    
    nodeQueue.Enqueue([origin]);

    while (nodeQueue.TryDequeue(out var path))
    {
        foreach (var neighbor in graph.GetValueOrDefault(path[^1], []))
        {
            string[] newPath = [..path, neighbor];

            if (newPath[^1] == destination)
            {
                return newPath;
            }
            
            nodeQueue.Enqueue(newPath);
        }
    }

    return null;
}

The only change compared to the previous algorithms is that we construct partial paths and enqueue a new path for each neighbor of the last node of the previous path.

iterative deepening