Don't get lost - Routing

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 soon as the graphs increase in size it becomes harder to tell if two nodes, in a given graph, are connected to each other. Let's see if computers can help us out before we dive into algorithms we need to discuss how we can represent these graphs in code.

We can represent the 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 interative deepening.

iterative deepening