using System.Collections.Generic;
using ConcurrentPriorityQueue;
public struct Distance<T> {
public class Graph<T> where T: class, IComparable<T> {
private readonly Dictionary<T, List<Edge>> _adj;
_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) {
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>();
var dist = new Dictionary<T, int>();
var path = new Dictionary<T, T>();
foreach(var n in _adj.Keys) {
foreach(var edge in _adj[cur]) {
var newDist = dist[cur] + edge.Weight;
if(newDist < dist[edge.Node]) {
dist[edge.Node] = newDist;
q.Enqueue(edge.Node, newDist);
Console.WriteLine("dist=[{0}]", string.Join(",", dist));
Console.WriteLine("path=[{0}]", string.Join(",", path));
for(var cur = path[start]; cur != null; cur = path.ContainsKey(cur) ? path[cur] : null) {
public readonly int Weight;
public Edge(T node, int 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);
Console.WriteLine("shortest path: {0}", string.Join("->", graph.FindShortestPath("a")));