gist/20171221/Djikstra.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

// Adapted from JavaScript example in The Imposter's Hanbook by Rob Conery
// Doesn't support negative edges!

namespace Djikstra
{
    class Path
    {
        public string Name;
        public int Cost;
        public bool Visited;

        public Path(string name, int cost, bool visited)
        {
            Name = name;
            Cost = cost;
            Visited = visited;
        }
    }

    class MemoTable
    {
        private List<Path> Table;
        public Path S;

        public MemoTable(string[] vertices)
        {
            S = new Path("S", 0, false);
            Table = new List<Path>() {S};

            foreach (var vertex in vertices)
            {
                Table.Add(new Path(vertex, int.MaxValue, false));
            }
        }

        private List<Path> GetCandidateVertices()
        {
            return Table.Where(x => !x.Visited).ToList();
        }

        public Path NextVertex()
        {
            List<Path> candidates = GetCandidateVertices();

            if (candidates.Any())
            {
                return candidates.OrderBy(x => x.Cost).First();
            }
            return null;
        }

        private Path GetEntry(string vertex) => Table.First(x => x.Name == vertex);

        private void SetCurrentCost(string vertex, int cost)
        {
            GetEntry(vertex).Cost = cost;
        }

        private void SetAsVisited(string vertex)
        {
            GetEntry(vertex).Visited = true;
        }

        private int GetCost(string vertex)
        {
            return GetEntry(vertex).Cost;
        }

        public void Evaluate(List<GraphItem> graph, Path vertex)
        {
            GraphItem[] edges = graph.Where(x => x.From == vertex.Name).ToArray();
            foreach (var edge in edges)
            {
                int currentVertexCost = GetCost(edge.From);
                int toVertexCost = GetCost(edge.To);
                int tentativeCost = currentVertexCost == int.MaxValue ? int.MaxValue : currentVertexCost + edge.Cost;
                if (tentativeCost < toVertexCost)
                    SetCurrentCost(edge.To, tentativeCost);
            }
            SetAsVisited(vertex.Name);

            Path next = NextVertex();
            if (next != null)
                Evaluate(graph, next);
        }

        public override string ToString()
        {
            StringBuilder buffer = new StringBuilder();
            foreach (var element in Table)
            {
                buffer.AppendLine($"name: {element.Name}, cost: {element.Cost}, visited: {element.Visited}");
            }
            return buffer.ToString();
        }
    }

    class GraphItem
    {
        public string From;
        public string To;
        public int Cost;

        public GraphItem(string from, string to, int cost)
        {
            From = from;
            To = to;
            Cost = cost;
        }
    }

    class Program
    {
        static string[] vertices = { "A", "B", "C", "D", "E" };

        static List<GraphItem> graph = new List<GraphItem>()
        {
            new GraphItem("S", "A", 4),
            new GraphItem("S", "E", 2),
            new GraphItem("A", "D", 3),
            new GraphItem("A", "C", 6),
            new GraphItem("A", "B", 5),
            new GraphItem("B", "A", 3),
            new GraphItem("C", "B", 1),
            new GraphItem("D", "C", 3),
            new GraphItem("D", "A", 1),
            new GraphItem("E", "D", 1)
        };

        static void Main()
        {
            MemoTable memo = new MemoTable(vertices);

            memo.Evaluate(graph, memo.S);

            Console.WriteLine(memo.ToString());
        }
    }
}