Facebook
From HaxorBonzo, 5 Years ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 220
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace ConsoleApplication65
  8. {
  9.  
  10.     class wierzcholek
  11.     {
  12.         public int wartosc;
  13.         public List<krawedz> kStart = new List<krawedz>();
  14.         public List<krawedz> kStop = new List<krawedz>();
  15.  
  16.         public wierzcholek(int wartosc)
  17.         {
  18.             this.wartosc = wartosc;
  19.         }
  20.  
  21.         public List<krawedz> test()
  22.         {
  23.             return kStart;
  24.         }
  25.  
  26.         public void wypiszGRAF()
  27.         {
  28.             Console.WriteLine("=================");
  29.             foreach (krawedz i in kStart)
  30.             {
  31.                 Console.WriteLine(i.start.wartosc + " => " + i.stop.wartosc + " waga: " +i.waga);
  32.             }
  33.             Console.WriteLine("=================");
  34.         }
  35.     }
  36.  
  37.     class krawedz
  38.     {
  39.         public int waga;
  40.         public wierzcholek start;
  41.         public wierzcholek stop;
  42.  
  43.         public krawedz(wierzcholek odKtorego, wierzcholek doKtorego, int waga)
  44.         {
  45.             this.waga = waga;
  46.             this.start = odKtorego;
  47.             this.stop = doKtorego;
  48.             odKtorego.kStart.Add(this);
  49.             doKtorego.kStop.Add(this);
  50.  
  51.         }
  52.     }
  53.  
  54.     class Program
  55.     {
  56.         static int[] SzukajMinimum( int[] d, bool[] t)
  57.         {
  58.             int[] wynik = new int[2];
  59.             int minimum = 2147483647;
  60.             for (int i = 0; i < d.Length; i++)
  61.             {
  62.                 if (t[i] == false)
  63.                 {
  64.                     if (d[i] < minimum)
  65.                     {
  66.                         minimum = d[i];
  67.                         wynik[0] = i;
  68.                     }
  69.                 }
  70.             }
  71.             wynik[1] = minimum;      
  72.             return wynik;
  73.         }
  74.  
  75.         static void Main(string[] args)
  76.         {
  77.  
  78.             wierzcholek wierzcholek0 = new wierzcholek(0);
  79.             wierzcholek wierzcholek1 = new wierzcholek(1);
  80.             wierzcholek wierzcholek2 = new wierzcholek(2);
  81.             wierzcholek wierzcholek3 = new wierzcholek(3);
  82.             wierzcholek wierzcholek4 = new wierzcholek(4);
  83.             wierzcholek wierzcholek5 = new wierzcholek(5);
  84.  
  85.  
  86.             krawedz krawedz1 = new krawedz(wierzcholek0, wierzcholek1, 3);
  87.             krawedz krawedz2 = new krawedz(wierzcholek1, wierzcholek2, 1);
  88.             krawedz krawedz3 = new krawedz(wierzcholek2, wierzcholek5, 1);
  89.             krawedz krawedz4 = new krawedz(wierzcholek4, wierzcholek5, 2);
  90.             krawedz krawedz5 = new krawedz(wierzcholek5, wierzcholek0, 6);
  91.             krawedz krawedz6 = new krawedz(wierzcholek3, wierzcholek1, 3);
  92.             krawedz krawedz7 = new krawedz(wierzcholek5, wierzcholek3, 1);
  93.             krawedz krawedz8 = new krawedz(wierzcholek0, wierzcholek4, 3);
  94.  
  95.             wierzcholek0.wypiszGRAF();
  96.             wierzcholek1.wypiszGRAF();
  97.             wierzcholek2.wypiszGRAF();
  98.             wierzcholek3.wypiszGRAF();
  99.             wierzcholek4.wypiszGRAF();
  100.             wierzcholek5.wypiszGRAF();
  101.  
  102.             int v = 0;
  103.             List<krawedz> Q = new List<krawedz>();
  104.             List<krawedz> S = new List<krawedz>();
  105.             int[] d = new int[6];
  106.             int[] p = new int[6];
  107.             bool[] t = new bool[6];
  108.             const int Infinity = 2147483647;
  109.             int[] min;
  110.  
  111.             Q.Add(krawedz1);
  112.             Q.Add(krawedz2);
  113.             Q.Add(krawedz3);
  114.             Q.Add(krawedz4);
  115.             Q.Add(krawedz5);
  116.             Q.Add(krawedz6);
  117.             Q.Add(krawedz7);
  118.             Q.Add(krawedz8);
  119.  
  120.             //INITIALIZE--------------------------------------------
  121.             for (int i = 0; i < 6; i++){
  122.                 if (v == i) d[v] = 0;
  123.                 else d[i] = Infinity;
  124.             }
  125.             for (int i = 0; i < 6; i++) p[i] = -1;
  126.             for (int i = 0; i < 6; i++) Console.WriteLine(d[i]);
  127.             for (int i = 0; i < 6; i++) Console.WriteLine(p[i]);
  128.             for (int i = 0; i < 6; i++) Console.WriteLine(t[i]);
  129.             //ENDINITIALIZE--------------------------------------------
  130.  
  131.             //DIJKSTRA
  132.             while(Q.Count != 0){
  133.             min = SzukajMinimum(d,t);
  134.             t[min[0]] = true;
  135.             foreach (krawedz i in Q) if (i.start.wartosc == min[0]) S.Add(i);
  136.             for (int i = Q.Count - 1; i >= 0; i--) if (Q[i].start.wartosc == min[0]) Q.RemoveAt(i);
  137.            
  138.             foreach (krawedz i in S)
  139.             {
  140.                 if (d[i.stop.wartosc] > i.waga+min[1])
  141.                 {
  142.                     d[i.stop.wartosc] = i.waga + min[1];
  143.                     p[i.stop.wartosc] = i.start.wartosc;
  144.                 }
  145.             }
  146.             Console.WriteLine("\r\n d[i] ================= \r\n");
  147.             for (int i = 0; i < 6; i++) Console.Write(d[i] + ", ");
  148.             Console.WriteLine("\r\n p[i] ================= \r\n");
  149.             for (int i = 0; i < 6; i++) Console.Write(p[i] + ", ");
  150.             Console.WriteLine("\r\n t[i] ================= \r\n");
  151.             for (int i = 0; i < 6; i++) Console.Write(t[i] + ", ");
  152.             S.Clear();
  153.             Console.WriteLine("\r\n=================/END KROK\r\n");
  154.             }
  155.             //ENDDIJKSTRA
  156.  
  157.  
  158.             Console.ReadKey();
  159.  
  160.         }
  161.     }
  162. }
  163.