Find shortest path (Breadth-First Search)

So, assuming we have a two-dimensional array that describes the connected points between two nodes. We want to find the shortest path between a starting and end point (but let's be realistic, one of the shortest will do as well!).

public static void FindShortestRoute(string start, string end, string[,] edges)
{
    var connectedNodes = CreateGraph(edges);
    if(!connectedNodes.ContainsKey(start) || !connectedNodes.ContainsKey(end))
    {
        Console.WriteLine("Start or End node doesn't exist in the graph.");
        return;
    }
    
    for (var i = 0; i < edges.GetLength(0); i++)
    {
        if (!connectedNodes.ContainsKey(edges[i, 0]))
        {
            connectedNodes[edges[i, 0]] = new List<string>();
        }

        connectedNodes[edges[i, 0]].Add(edges[i, 1]);
    }

    var queue = new Queue<string>();
    queue.Enqueue(start);

    var visited = new HashSet<string>();
    visited.Add(start);

    var path = new Dictionary<string, string>();

    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        if (node == end)
        {
            var shortestPath = new List<string>();
            var currentNode = end;

            while (currentNode != null)
            {
                shortestPath.Add(currentNode);
                path.TryGetValue(currentNode, out currentNode);
            }

            shortestPath.Reverse();
            Console.WriteLine("Shortest path: " + string.Join(" -> ", shortestPath));
            return;
        }

        foreach (var neighbor in connectedNodes[node].Where(neighbor => visited.Add(neighbor)))
        {
            queue.Enqueue(neighbor);

            path.TryAdd(neighbor, node);
        }
    }
}

private static Dictionary<string, List<string>> CreateGraph(string[,] edges)
{
    var connectedNodes = new Dictionary<string, List<string>>();

    for (var i = 0; i < edges.GetLength(0); i++)
    {
        if (!connectedNodes.TryGetValue(edges[i, 0], out var value))
        {
            value = new List<string>();
            connectedNodes[edges[i, 0]] = value;
        }

        value.Add(edges[i, 1]);
    }

    PrintEdges(edges);
    PrintConnectedNodes(connectedNodes);
    
    return connectedNodes;
}

private static void PrintEdges(string[,] edges)
{
    StringBuilder result = new StringBuilder();

    for (int i = 0; i < edges.GetLength(0); i++)
    {
        result.AppendLine($"{i+1}: {edges[i, 0]}, {edges[i, 1]}");
    }
    Console.WriteLine("Pairs:");
    Console.WriteLine(result);
}

private static void PrintConnectedNodes(Dictionary<string, List<string>> connectedNodes)
{
    var printOutDictionary =  string.Join(Environment.NewLine, 
        connectedNodes.Select(kvp => $"Key: {kvp.Key}, Value: {string.Join(',', kvp.Value)}"));
    Console.WriteLine("Connected nodes:");
    Console.WriteLine(printOutDictionary);
}

Let's break it down:
CreateGraph(edges) method is called, which constructs a Dictionary<string, List<string>> where the key is a node and the value is a list of nodes directly connected to that node. This represents adjacency list representation of a graph. PrintEdges(edges) and PrintConnectedNodes(connectedNodes) methods are also called within it to print out all the edges in the graph and nodes with their connections respectively.

Then, it checks if the start or the end nodes exist in the graph by checking if they are keys in the returned dictionary. If they do not exist, it prints a message and returns.

It initializes a queue queue to hold the nodes to visit, a hash-set visited to track the visited nodes and a dictionary path to remember the path from the start node.

Now, it starts traversing the graph from the start node and adds it to the queue and the visited nodes set. Then, for each vertex, it checks its adjacent/unvisited nodes and adds them into the queue to be visited later, and also adds them into the path dictionary with the current "node" as the value. The process continues until there are no more nodes to visit or the end node is found.

If the end node is found, it backtracks from the end node to the start node using the path dictionary, and this forms the shortest path. It prints this path and the function ends.

Running it like this:

FindShortestRoute("a","f", new[,]
{
    { "a", "d" },
    { "d", "c" },
    { "d", "a" },
    { "b", "e" },// short path, 2
    { "e", "c" },
    { "c", "a" },
    { "f", "e" },
    { "a", "b" },// short path, 1
    { "e", "c" },
    { "e", "f" },// short path, 3
    { "a", "b" },
    { "b", "c" },
    { "c", "d" }
});

Please keep in mind, that we do not use weighted edges!

No files yet, migration hasn't completed yet!