Dijkstra's algorithm... yayyyy.....

Dijkstra.cs

using System;
using System.Linq;
using System.Collections.Generic;
using NodeId = System.String;

namespace dijkstra
{
    class Program
    {
        static void Main(string[] args)
        {
            //  Visual representation of Graph
            //  +--------------[F]------ 9 -----[E]
            //  |               |                |
            //  |               2                6
            //  |               |                |
            //  |     +--------[C]----- 11 -----[D]
            //  |     |         |                |
            // 14     |         |                |
            //  |     9        10               14
            //  |     |         |                |
            //  |     |         |                |
            //  +----[A]-- 7 --[B]---------------+

            //  Calculate shortest path
            var path = Dijkstra.ShortestPath(startNode: "A",
                                             endNode:   "E",
                                             graph:     new Graph("A",  7, "B",
                                                                  "A",  9, "C",
                                                                  "B", 10, "C",
                                                                  "B", 14, "D",
                                                                  "A", 14, "F",
                                                                  "C",  2, "F",
                                                                  "C", 11, "D",
                                                                  "F",  9, "E",
                                                                  "D",  6, "E"));

            // Write all graph history
            path.History.Each(g => $"{g}\n".WriteLine());

            // Write all the nodes
            path.Nodes().Join(" -> ").WriteLine(label: "* Path/Solution:");

            // Output
            // * Graph Generation: 0
            // ** Node: A, Pending
            // ** Node: B, Pending
            // ** Node: C, Pending
            // ** Node: D, Pending
            // ** Node: F, Pending
            // ** Node: E, Pending
            //
            // * Graph Generation: 1
            // ** Node: A, Score: 0, Source: A
            // ** Node: B, Pending
            // ** Node: C, Pending
            // ** Node: F, Pending
            // ** Node: D, Pending
            // ** Node: E, Pending
            //
            // * Graph Generation: 2
            // ** Node: A, Score: 0, Source: A
            // ** Node: B, Score: 7, Source: A
            // ** Node: C, Pending
            // ** Node: F, Pending
            // ** Node: D, Pending
            // ** Node: E, Pending
            //
            // * Graph Generation: 3
            // ** Node: A, Score: 0, Source: A
            // ** Node: B, Score: 7, Source: A
            // ** Node: C, Score: 9, Source: A
            // ** Node: F, Pending
            // ** Node: D, Pending
            // ** Node: E, Pending
            //
            // * Graph Generation: 4
            // ** Node: A, Score: 0, Source: A
            // ** Node: B, Score: 7, Source: A
            // ** Node: C, Score: 9, Source: A
            // ** Node: F, Score: 11, Source: C
            // ** Node: D, Pending
            // ** Node: E, Pending
            //
            // * Graph Generation: 5
            // ** Node: A, Score: 0, Source: A
            // ** Node: B, Score: 7, Source: A
            // ** Node: C, Score: 9, Source: A
            // ** Node: F, Score: 11, Source: C
            // ** Node: D, Pending
            // ** Node: E, Score: 20, Source: F
            //
            // * Graph Generation: 6
            // ** Node: A, Score: 0, Source: A
            // ** Node: B, Score: 7, Source: A
            // ** Node: C, Score: 9, Source: A
            // ** Node: F, Score: 11, Source: C
            // ** Node: D, Score: 20, Source: C
            // ** Node: E, Score: 20, Source: F
            //
            // * Path/Solution: A -> C -> F -> E
        }
    }

    public static class Dijkstra
    {
        public static Path ShortestPath(NodeId startNode,
                                        NodeId endNode,
                                        Graph graph)
        {
            var history = new List<Graph> { graph };

            return new Path(startNode,
                            endNode,
                            ShortestPathRecur(startNode,
                                              endNode,
                                              graph,
                                              nodeToScore: startNode,
                                              history: history));
        }

        static List<Graph> ShortestPathRecur(NodeId startNode,
                                             NodeId endNode,
                                             Graph graph,
                                             NodeId nodeToScore,
                                             List<Graph> history)
        {
            if (nodeToScore == null) return history;

            var nextGraph = graph.DeepClone();

            if (nodeToScore == startNode) nextGraph.SetScore(nodeToScore, 0);

            nextGraph.Neighbors(of: nodeToScore)
                     .Each(neighbor => nextGraph.ScoreNeighbor(source: nodeToScore,
                                                               neighbor: neighbor));

            nextGraph.MarkComplete(nodeToScore);

            history.Add(nextGraph);

            return ShortestPathRecur(startNode,
                                     endNode,
                                     graph:       nextGraph,
                                     nodeToScore: nextGraph.PendingNeighbor(of: nodeToScore),
                                     history:     history);
        }
    }

    public class Path
    {
        public NodeId StartNode { get; set; }
        public NodeId EndNode { get; set; }
        public List<Graph> History { get; set; }

        public Path(NodeId startNode, NodeId endNode, List<Graph> history)
        {
            StartNode = startNode;
            EndNode   = endNode;
            History   = history;
        }

        public IEnumerable<NodeId> Nodes()
        {
            return ResultRecur(History.Last(),
                               new List<NodeId> { EndNode }).ReverseEx();
        }

        List<NodeId> ResultRecur(Graph graph, List<NodeId> path)
        {
            var lastNode = path.LastOrDefault();

            if (lastNode == StartNode) return path;

            return ResultRecur(graph,
                               path.AppendEx(graph.ScoreSource[lastNode]));
        }
    }

    public class Graph
    {
        public int Generation { get; set; } = 0;
        public Dictionary<NodeId, Dictionary<NodeId, int>> Edges = new Dictionary<NodeId, Dictionary<NodeId, int>>();
        public Dictionary<NodeId, bool> Completed = new Dictionary<NodeId, bool>();
        public Dictionary<NodeId, NodeId> ScoreSource { get; set; } = new Dictionary<NodeId, NodeId>();
        public Dictionary<NodeId, int> Scores { get; set; } = new Dictionary<NodeId, int>();

        public Graph() { }

        public Graph(NodeId from, int distance, NodeId to, params object[] rest)
        {
            AddConnection(from, distance, to);
            rest.EachThree<NodeId, int, NodeId>(AddConnection);
        }

        public int Score(NodeId node) => Scores[node];

        public void AddConnection(NodeId from, int distance, NodeId to)
        {
            AddNode(from);
            AddNode(to);
            AddEdge(from, distance, to);
        }

        public void AddEdge(NodeId from, int distance, NodeId to)
        {
            edges.SafeGetOrNew(from)[to] = distance;
            edges.SafeGetOrNew(to)[from] = distance;
        }

        public void AddNode(NodeId node)
        {
            Scores[node] = int.MaxValue;
            completed[node] = false;
        }

        public void MarkComplete(NodeId node) => completed[node] = true;

        public IEnumerable<NodeId> Neighbors(NodeId of) => edges[of].Keys;

        public void ScoreNeighbor(NodeId source, NodeId neighbor) =>
            SetScore(node:   neighbor,
                     value:  Distance(source, neighbor) + Score(source),
                     source: source);

        public void SetScore(NodeId node, int value) => SetScore(node, value, null);

        public void SetScore(NodeId node, int value, NodeId source)
        {
            if (Scores[node] < value) return;

            Scores[node] = value;

            if (source != null) ScoreSource[node] = source;
        }

        public int Distance(NodeId node, NodeId otherNode) => edges[node][otherNode];

        public Graph DeepClone()
        {
            var clone = new Graph();

            clone.Generation = Generation + 1;

            edges.Each((node, neighbors) =>
            {
                neighbors.Each((otherNode, distance) =>
                {
                    clone.AddConnection(node, distance, otherNode);
                });
            });

            Scores.Each((node, score) => clone.Scores[node] = score);

            ScoreSource.Each((node, sourceNode) => clone.ScoreSource[node] = sourceNode);

            completed.FilterEach(filter: (_, hasBeenScored) => hasBeenScored,
                                 action: (node, _) => clone.MarkComplete(node));

            return clone;
        }

        public NodeId PendingNeighbor(NodeId of) => PendingNeighbors(of).FirstOrDefault();

        public IEnumerable<NodeId> PendingNeighbors(NodeId of) => Neighbors(of).Where(IsPending);

        public bool IsPending(NodeId node) => !completed[node];

        string NodeToString(string node)
        {
            if (IsPending(node)) return $"** Node: {node}, Pending";

            return $"** Node: {node}, Score: {Scores[node]}, Source: {ScoreSource.SafeGetOrDefault(node, node)}";
        }

        public override string ToString()
        {
            var strings = new List<string>();
            strings.Add($"* Graph Generation: {Generation}");
            Scores.Each((node, score) => strings.Add(NodeToString(node)));
            return strings.Join("\n");
        }
    }

    static class Extensions
    {
        // debugging extensions
        public static T WriteLine<T>(this T o, string label = "")
        {
            if (label != string.Empty) label = label + " ";
            Console.WriteLine($"{label}{o}");
            return o;
        }

        // enumeration extensions
        public static void Times(this int t, Action<int> action)
        {
            for(var i = 0; i < t; i++) action(i);
        }

        public static void Each<T1, T2>(this Dictionary<T1, T2> dict, Action<T1, T2> action)
        {
            dict.Keys.Each(k => action(k, dict[k]));
        }

        public static void Each<T1>(this IEnumerable<T1> list, Action<T1> action)
        {
            foreach (var l in list) action(l);
        }

        public static void EachThree<T1, T2, T3>(this object[] list, Action<T1, T2, T3> action)
        {
            (list.Length / 3).Times(i => action((T1)list[i * 3], (T2)list[i * 3 + 1], (T3)list[i * 3 + 2]));
        }

        public static void FilterEach<T1, T2>(this Dictionary<T1, T2> dict, Func<T1, T2, bool> filter, Action<T1, T2> action)
        {
            dict.Keys
                .Where(k => filter(k, dict[k]))
                .Each(k => action(k, dict[k]));
        }

        // dictionary extensions
        public static T2 SafeGetOrDefault<T1, T2>(this Dictionary<T1, T2> dict, T1 key, T2 defaultValue)
        {
            if (!dict.ContainsKey(key)) return defaultValue;
            return dict[key];
        }

        public static T2 SafeGetOrNew<T1, T2>(this Dictionary<T1, T2> dict, T1 key) where T2 : new()
        {
            if (!dict.ContainsKey(key)) dict.Add(key, new T2());
            return dict[key];
        }

        // list extensions
        public static IEnumerable<T> ReverseEx<T>(this List<T> list)
        {
            var result = new List<T>(list);
            result.Reverse();
            return result;
        }

        public static List<T> AppendEx<T>(this List<T> list, T value)
        {
            list.Add(value);
            return list;
        }

        public static string Join<T>(this IEnumerable<T> list, string delimiter)
        {
            return string.Join(delimiter, list);
        }
    }
}