- 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();
- }
- }
- }