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

namespace ConsoleApplication65
{

    class wierzcholek
    {
        public int wartosc;
        public List<krawedz> kStart = new List<krawedz>();
        public List<krawedz> kStop = new List<krawedz>();
 
        public wierzcholek(int wartosc)
        {
            this.wartosc = wartosc;
        }

        public List<krawedz> test()
        {
            return kStart;
        }

        public void wypiszGRAF()
        {
            Console.WriteLine("=================");
            foreach (krawedz i in kStart)
            {
                Console.WriteLine(i.start.wartosc + " => " + i.stop.wartosc + " waga: " +i.waga);
            }
            Console.WriteLine("=================");
        }
    }

    class krawedz
    {
        public int waga;
        public wierzcholek start;
        public wierzcholek stop;

        public krawedz(wierzcholek odKtorego, wierzcholek doKtorego, int waga)
        {
            this.waga = waga;
            this.start = odKtorego;
            this.stop = doKtorego;
            odKtorego.kStart.Add(this);
            doKtorego.kStop.Add(this);

        }
    }

    class Program
    {
        static int[] SzukajMinimum( int[] d, bool[] t)
        {
            int[] wynik = new int[2];
            int minimum = 2147483647;
            for (int i = 0; i < d.Length; i++)
            {
                if (t[i] == false)
                {
                    if (d[i] < minimum)
                    {
                        minimum = d[i];
                        wynik[0] = i;
                    }
                }
            }
            wynik[1] = minimum;       
            return wynik;
        }

        static void Main(string[] args)
        {

            wierzcholek wierzcholek0 = new wierzcholek(0);
            wierzcholek wierzcholek1 = new wierzcholek(1);
            wierzcholek wierzcholek2 = new wierzcholek(2);
            wierzcholek wierzcholek3 = new wierzcholek(3);
            wierzcholek wierzcholek4 = new wierzcholek(4);
            wierzcholek wierzcholek5 = new wierzcholek(5);


            krawedz krawedz1 = new krawedz(wierzcholek0, wierzcholek1, 3);
            krawedz krawedz2 = new krawedz(wierzcholek1, wierzcholek2, 1);
            krawedz krawedz3 = new krawedz(wierzcholek2, wierzcholek5, 1);
            krawedz krawedz4 = new krawedz(wierzcholek4, wierzcholek5, 2);
            krawedz krawedz5 = new krawedz(wierzcholek5, wierzcholek0, 6);
            krawedz krawedz6 = new krawedz(wierzcholek3, wierzcholek1, 3);
            krawedz krawedz7 = new krawedz(wierzcholek5, wierzcholek3, 1);
            krawedz krawedz8 = new krawedz(wierzcholek0, wierzcholek4, 3);

            wierzcholek0.wypiszGRAF();
            wierzcholek1.wypiszGRAF();
            wierzcholek2.wypiszGRAF();
            wierzcholek3.wypiszGRAF();
            wierzcholek4.wypiszGRAF();
            wierzcholek5.wypiszGRAF();

            int v = 0;
            List<krawedz> Q = new List<krawedz>();
            List<krawedz> S = new List<krawedz>();
            int[] d = new int[6];
            int[] p = new int[6];
            bool[] t = new bool[6];
            const int Infinity = 2147483647;
            int[] min;

            Q.Add(krawedz1);
            Q.Add(krawedz2);
            Q.Add(krawedz3);
            Q.Add(krawedz4);
            Q.Add(krawedz5);
            Q.Add(krawedz6);
            Q.Add(krawedz7);
            Q.Add(krawedz8);

            //INITIALIZE--------------------------------------------
            for (int i = 0; i < 6; i++){
                if (v == i) d[v] = 0;
                else d[i] = Infinity;
            }
            for (int i = 0; i < 6; i++) p[i] = -1;
            for (int i = 0; i < 6; i++) Console.WriteLine(d[i]);
            for (int i = 0; i < 6; i++) Console.WriteLine(p[i]);
            for (int i = 0; i < 6; i++) Console.WriteLine(t[i]);
            //ENDINITIALIZE--------------------------------------------

            //DIJKSTRA
            while(Q.Count != 0){
            min = SzukajMinimum(d,t);
            t[min[0]] = true;
            foreach (krawedz i in Q) if (i.start.wartosc == min[0]) S.Add(i);
            for (int i = Q.Count - 1; i >= 0; i--) if (Q[i].start.wartosc == min[0]) Q.RemoveAt(i);
            
            foreach (krawedz i in S)
            {
                if (d[i.stop.wartosc] > i.waga+min[1])
                {
                    d[i.stop.wartosc] = i.waga + min[1];
                    p[i.stop.wartosc] = i.start.wartosc;
                }
            }
            Console.WriteLine("\r\n d[i] ================= \r\n");
            for (int i = 0; i < 6; i++) Console.Write(d[i] + ", ");
            Console.WriteLine("\r\n p[i] ================= \r\n");
            for (int i = 0; i < 6; i++) Console.Write(p[i] + ", ");
            Console.WriteLine("\r\n t[i] ================= \r\n");
            for (int i = 0; i < 6; i++) Console.Write(t[i] + ", ");
            S.Clear();
            Console.WriteLine("\r\n=================/END KROK\r\n");
            }
            //ENDDIJKSTRA


            Console.ReadKey();

        }
    }
}