class Graf
    {
        public List<Node> Nodes;
        public List<Krawędź> Krawędzie;
        public List<Node> odwiedzone;
        public List<Node> zwracanieWęzłów;
        public Dictionary<Node, Para> odległości;
        public List<Krawędź> ZnajdźKrawędzie(Node n)
        {
            return this.Krawędzie.Where(k => k.start == n || k.koniec == n).ToList();
        }
        public Graf(int wartość)
        {
            Krawędzie = new List<Krawędź>();
            Nodes = new List<Node>();
        }
        public string SPA(Node start, Node koniec)
        {
            this.odwiedzone = new List<Node>();
            this.zwracanieWęzłów = new List<Node>();
            this.odległości = new Dictionary<Node, Para>();
            this.AD(start);
            this.ZwróćKolejnoWęzły(koniec);
            return "Najszybsza droga między węzłami  " + start + " i " + koniec + "  to: " + string.Join(" ", this.zwracanieWęzłów)
                + " i wynosi ona " + Convert.ToInt32(odległości[koniec].odległość) + " jed.";
        }
        public void AD(Node n)
        {
            if (this.odwiedzone.Contains(n))
                return;
            if (odwiedzone.Count == 0)
                this.odległości.Add(n, new Para(null, 0));
            this.odwiedzone.Add(n);
            List<Krawędź> kr = this.ZnajdźKrawędzie(n);
            // poniższy foreach dodaje do słownika "odległości" kolejne elementy w postaci
            // (następny węzeł, (akutalny węzeł, najszybsza droga do tego węzła)).
            // Jeśli dany klucz już istnieje w słowniku to else rozpatruje czy aktualna droga nie jest szybsza,
            // a jeżeli jest to podmienia wartość dla tego klucza(czyli ostatni zapisany do tego klucza węzeł na aktualny węzeł
            // oraz ostatnią zapisaną drogę na aktualną drogę)
            foreach (var k in kr)
            {
                if (!this.odwiedzone.Contains(k.WeźDrugi(n)))
                {
                    if (!odległości.ContainsKey(k.WeźDrugi(n)))
                        this.odległości.Add(k.WeźDrugi(n), new Para(n, k.waga + odległości[n].odległość));
                    else
                        if (this.odległości[k.WeźDrugi(n)].odległość > k.waga + odległości[n].odległość)
                        this.odległości[k.WeźDrugi(n)] = new Para(n, k.waga + odległości[n].odległość);
                }
            }
            // poniższy foreach wywołuje metodę AD(node n) gdzie n jest kluczem w słowniku z najmniejszą wartością drogi, który nie jest jeszcze dodany do odwiedzone
            // np ze słownika odległości=(2,(1-6)), (3,(1-4)), (4,(3-8)); wywoła element nr 1(czyli drugi,bo wartość jego  drogi wynosi 4).
            // Zostaje wywołana metoda AD(3), bo kluczem elementu nr 1 jest właśnie węzeł trzeci.
            foreach (var k in kr)
            {
                if (!this.odwiedzone.Contains(k.WeźDrugi(n)))
                    AD(odległości.OrderBy(x => x.Value.odległość).First(x => !this.odwiedzone.Contains(x.Key)).Key);
            }
        }
        public void ZwróćKolejnoWęzły(Node ostatni)
        {
            // metoda ta dostaje na początku węzeł do którego chcieliśmy się dostać
            // a następnie dodaje do listy zwracanieWęzłow każdy węzeł który zostanie wywołany.
            // Następny węzeł do wywołania to poprzednik naszego aktualnego węzła, czyli klucza w danym elemencie słownika odległości
            // np jezeli nasz węzeł do którego chcemy sie dostać to 4 to szukamy w słowniku elementu z kluczem 4 (np. (4,2-8)),
            // a następnie wywołujemy jego poprzednika czyli węzeł 2, następnie znowu szukamy elementu z kluczem 2 (np. (2,1-2)),
            // a ze to jest początkowy węzeł naszej drogi który nie ma poprzednika (np (1,null-0)) to zamiast zwracania poprzednika
            // odwracamy listę zwracanieWęzłów (inaczej lista szła by od ostatniego do pierwszego elementu drogi)
            zwracanieWęzłów.Add(ostatni);
            Node poprzednik = this.odległości[ostatni].n;
            if (poprzednik != null)
                ZwróćKolejnoWęzły(poprzednik);
            else
                zwracanieWęzłów.Reverse();
        }
    }