מריה בוטוסוב

יש למצוא מסלול הכי קצר עם התחשבות לזמן שלוקח להגיעה מנקודה לנקודה.

class Program
{
   static void Main(string[] args)
    {
        Graph g = new Graph();
        g.addVertex('A', new Dictionary<char, int>() { { 'B', 7 }, { 'C', 8 } });
        g.addVertex('B', new Dictionary<char, int>() { { 'A', 7 }, { 'F', 2 } });
        g.addVertex('C', new Dictionary<char, int>() { { 'A', 8 }, { 'F', 6 }, { 'G', 4 } });
        g.addVertex('D', new Dictionary<char, int>() { { 'F', 8 } });
        g.addVertex('E', new Dictionary<char, int>() { { 'H', 1 } });
        g.addVertex('F', new Dictionary<char, int>() { { 'B', 2 }, { 'C', 6 }, { 'D', 8 }, { 'G', 9 }, { 'H', 3 } });
        g.addVertex('G', new Dictionary<char, int>() { { 'C', 4 }, { 'F', 9 } });
        g.addVertex('H', new Dictionary<char, int>() { { 'E', 1 }, { 'F', 3 } });
 
        g.shortestPath('A', 'H').ForEach(x => Console.WriteLine(x));
        Console.ReadKey();
    }
}
 
 
class Graph
{
    Dictionary<char, Dictionary<char, int>> vertices = new Dictionary<char, Dictionary<char, int>>();
    public void addVertex(char name, Dictionary<char, int> edges)
    {
        vertices[name] = edges;
    }
    public List<char> shortestPath(char start, char finish)
    {
        var previous = new Dictionary<char, char>();
        var distances = new Dictionary<char, int>();
        var nodes = new List<char>();
        List<char> path = null;
 
        foreach (var vertex in vertices)
        {
            if (vertex.Key == start)
                distances[vertex.Key] = 0;
            else
                distances[vertex.Key] = int.MaxValue;
 
            nodes.Add(vertex.Key);
        }
        while (nodes.Count != 0)
        {
            nodes.Sort((x, y) => distances[x] - distances[y]);
 
            var smallest = nodes[0];
            nodes.Remove(smallest);
 
            if (smallest == finish)
            {
                path = new List<char>();
                while (previous.ContainsKey(smallest))
                {
                    path.Add(smallest);
                    smallest = previous[smallest];
                }
                break;
            }
 
            if (distances[smallest] == int.MaxValue)                
                break;
 
            foreach (var neighbor in vertices[smallest])
            {
                var alt = distances[smallest] + neighbor.Value;
                if (alt < distances[neighbor.Key])
                {
                    distances[neighbor.Key] = alt;
                    previous[neighbor.Key] = smallest;
                }
            }
        }
        return path;
    }
}