Project · Algorithms

Graph route

Find one shortest route in an unweighted graph using predecessor links.

Open project in playground ← All projects

All C# source files below are loaded together in the playground. Files written by a run live in its virtual directory.

Program.cs

using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Threading;
using System.Threading.Tasks;

var graph = new Dictionary<string, string[]> { ["A"] = new[] { "B", "C" }, ["B"] = new[] { "D" }, ["C"] = new[] { "E" }, ["D"] = new[] { "E" }, ["E"] = Array.Empty<string>() };
var route = Routes.Find(graph, "A", "E");
Console.WriteLine(route.Length == 0 ? "No route" : string.Join(" -> ", route));

Algorithms/Routes.cs

using System.Collections.Generic;
public static class Routes
{
    public static string[] Find(IReadOnlyDictionary<string, string[]> graph, string start, string goal)
    {
        var queue = new Queue<string>();
        var previous = new Dictionary<string, string?> { [start] = null };
        queue.Enqueue(start);
        while (queue.Count > 0)
        {
            var node = queue.Dequeue();
            if (node == goal)
            {
                var path = new List<string>();
                for (string? current = goal; current != null; current = previous[current]) path.Add(current);
                path.Reverse();
                return path.ToArray();
            }
            if (!graph.TryGetValue(node, out var neighbors)) continue;
            foreach (var next in neighbors) if (previous.TryAdd(next, node)) queue.Enqueue(next);
        }
        return System.Array.Empty<string>();
    }
}

Graphroute.csproj

<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net9.0</TargetFramework>
    <ImplicitUsings>enable</ImplicitUsings>
    <Nullable>enable</Nullable>
  </PropertyGroup>
</Project>