using System;

using System.Linq;

using System.Collections.Generic;

using ConcurrentPriorityQueue;

​

public struct Distance<T> {

    public int Value;

    public T Node;

}

​

public class Program

{   

    public class Graph<T> where T: class, IComparable<T> {

        private readonly Dictionary<T, List<Edge>> _adj;

        public Graph() {

            _adj = new Dictionary<T, List<Edge>>();

        }

        public void AddEdge(T source) {

            _adj[source] = new List<Edge>();

        }

        public void AddEdge(T source, T dest, int weight) {

            List<Edge> verticies;

            if(!_adj.TryGetValue(source, out verticies)) {

                verticies = new List<Edge>();

            }

            verticies.Add(new Edge(dest, weight));

            _adj[source] = verticies;

        }

        public T[] FindShortestPath(T start) {

            var q = new ConcurrentPriorityQueue<T, int>();

            q.Enqueue(start, 0);

            var dist = new Dictionary<T, int>();

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

            var s = new Stack<T>();

            foreach(var n in _adj.Keys) {

                dist[n] = int.MaxValue;

            }

            dist[start] = 0;

            while(q.Count() > 0) {

                var cur = q.Dequeue();

                foreach(var edge in _adj[cur]) {

                    var newDist = dist[cur] + edge.Weight;

                    if(newDist < dist[edge.Node]) {

                        dist[edge.Node] = newDist;

                        //it's invalid we should check if it's in Queue, if it is, decrease key

                        q.Enqueue(edge.Node, newDist);

                        path[cur] = edge.Node;

                    }

                }

            }

            Console.WriteLine("dist=[{0}]", string.Join(",", dist));

            Console.WriteLine("path=[{0}]", string.Join(",", path));

            s.Push(start);

            for(var cur = path[start]; cur != null; cur = path.ContainsKey(cur) ? path[cur] : null) {

                s.Push(cur);

            }

            return s.ToArray();

        }

        private class Edge {

            public readonly T Node;

            public readonly int Weight;

            public Edge(T node, int weight) {

                Node = node;

                Weight = weight;

            }

        }

    }

    public static void Main()

    {

        var graph = new Graph<string>();

        graph.AddEdge("a", "b", 2);

        graph.AddEdge("a", "c", 50);

        graph.AddEdge("b", "c", 3);

        graph.AddEdge("c", "e", 4);

        graph.AddEdge("e", "y", 17);    

        graph.AddEdge("y");

        Console.WriteLine("shortest path: {0}", string.Join("->", graph.FindShortestPath("a")));

    }

}