Schemat blokowy algorytmu Dijkstry

Question

Witam, potrzebuję schematu blokowego algorytmu Dijkstry spójnego z kodem:

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

namespace algorytm_dijkstry
{
    class Program
    {

        static int IlośćKrawedzi()
        {
            string[] file = File.ReadAllLines(Path.Combine(@"C:\Users\Marcin\Desktop\Projekt\graf.txt"));
            int x = file.Length - 1;
            return x;
        }

        static int IlośćWierzcholkow()
        {
            string[] file = File.ReadAllLines(Path.Combine(@"C:\Users\Marcin\Desktop\Projekt\graf.txt"));
            int x = file.Length - 1;
            int z = 0;
            try
            {
                z = Convert.ToInt32(file[x]);
            }
            catch (Exception)
            {
                Console.WriteLine("Nieprawidłowy format pliku z grafem ");
                Console.ReadLine(); throw;
            }

            return z;
        }

        static string[] Czytanie()
        {

            string[] file = File.ReadAllLines(Path.Combine(@"C:\Users\Marcin\Desktop\Projekt\graf.txt"));
            return file;
        }

        static int[,] CzytajGraf()
        {

            int n = IlośćKrawedzi();
            string[] graf = new string[n];
            graf = Czytanie();

            int[,] grav = new int[n, 3];

            for (int i = 0; i < n; i++)
            {


                string[] Foo = graf[i].Split(new char[] { ' ' });
                int j = 0;
                foreach (string Bar in Foo)
                {
                    int x = 0;

                    x = Convert.ToInt32(Bar);


                        if (j >= 0 && j <= 1 && x >= 0 && x < IlośćWierzcholkow())
                    {
                        grav[i, j] = x;
                        j++;
                    }
                    else if (j==2 && x > 0)
                    {
                        grav[i, j] = x;
                        j++;
                    }
                    else
                    {
                        Console.WriteLine("Nieprawidłowy format pliku z grafem, zajrzyj do intrukcji.");
                        Console.ReadLine();
                        Environment.Exit(1);
                        break;
                    }
                }
            }

            return grav;

        }


        static int SzuknieNajD(bool[] QS, int[] d)
        {
            int min = 0;
            for (int i = 0; i < IlośćWierzcholkow(); i++) 
            {
                if (QS[i]==true)
                {
                    min = i;
                }
            }

            for (int i = 0; i < IlośćWierzcholkow(); i++) 
            {
                if (QS[i]==true && d[i] < d[min])
                {
                    min = i;
                }
            }
            return min;
        }

        static void Dijkstry(int start, int[,] graf, int koniec)

        {
            int[] d = new int[IlośćWierzcholkow()];
            int[] p = new int[IlośćWierzcholkow()];
            bool[] QS = new bool[IlośćWierzcholkow()];

            for (int i = 0; i < IlośćWierzcholkow(); i++)
            {
                QS[i] = true;
            }

            for (int i = 0; i < IlośćWierzcholkow(); i++) //poczatkowe wartości tablicy
            {
                d[i] = 1000;
                p[i] = -1;
                if (i==start)
                {
                    d[i] = 0;
                }
            }

            int najm;
            najm = SzuknieNajD(QS, d);
            QS[najm] = false; //wykluczenie wierzchołka startu

            for (int j = 0; j < IlośćWierzcholkow(); j++)
            {

                for (int i = 0; i < IlośćKrawedzi(); i++)
                {
                    if (graf[i, 0]==najm)
                    {
                        if (d[graf[i, 1]] > d[najm] + graf[i, 2]) //weryfikacja, czy nowy koszt jest mniejszy od starego
                        {
                            d[graf[i, 1]] = d[najm] + graf[i, 2]; //nadpisanie kosztu
                            p[graf[i, 1]] = najm; // nadpisanie poprzednika
                        }
                    }

                }
                najm = SzuknieNajD(QS, d); // wyszukanie kolejnego wierzcholka
                QS[najm] = false; //wyeliminowanie kolejnego wierzcholka
            }

            if (d[koniec] != 1000)
            {
                Console.WriteLine("Łączny koszt od wierzchołka " + start.ToString() + " do wierzchołka " + koniec.ToString() + " to: " + d[koniec].ToString());
                int[] trasa = new int[IlośćWierzcholkow()];
                for (int i = 0; i < IlośćWierzcholkow(); i++)
                {
                    trasa[i] = -1;
                }

                for (int i = 0; i < IlośćWierzcholkow(); i++)
                {
                    trasa[i] = koniec;
                    if (p[koniec]==start)
                    {
                        trasa[i + 1] = start;
                        break;
                    }
                    koniec = p[koniec];

                }

                Console.WriteLine("Najkrótsza droga to:");
                for (int i = IlośćWierzcholkow() - 1; i > -1; i--)
                {
                    if (trasa[i] != -1)
                    {
                        Console.Write(trasa[i].ToString() + " ");
                    }

                }
            }
            else
            {
                Console.WriteLine("Nie ma drogi od wierzchołka " + start.ToString() + " do wierzchołka " + koniec.ToString());
            }

        }

        static void Main(string[] args)
        {

            int[,] graf = new int[IlośćKrawedzi(), 3];
            graf = CzytajGraf();
            int start = 0;
            int koniec = 1;


            Console.WriteLine("Podaj wierzchołek startu:");

            start = Int32.Parse(Console.ReadLine());

            Console.WriteLine("Podaj wierzchołek końca:");

            koniec = Int32.Parse(Console.ReadLine());

            Dijkstry(start, graf, koniec);


            Console.ReadLine();

        }
    }
}

Answer 1

To go zaimplementuj ? .... korzystając z kodu? Czemu ktoś ma to zrobić za Ciebie ...

Answer 2

Dijkstra

W wierzchołku startowym dajemy wagę dojścia „zero”;
dla tego wierzchołka odwiedzony := true;
w pozostałych wierzchołkach dajemy wagę dojścia na nieskończoność
repeat
    znajdujemy nieodwiedzony wierzchołek o najmniejszej wadze dojścia; 
    if są wierzchołki nieodwiedzone
    then
    begin
       znaleziony nieodwiedzony wierzchołek o najmniejszej wadze dojścia zaznaczamy jako 	odwiedzony;
       jeśli ten znaleziony  wierzchołek o najmniejszej wadze dojścia jest poszukiwanym 	wierzchołkiem
       then
          exit;
       for wszystkich nieodwiedzonych sąsiadów wierzchołka do
       begin
          if  waga dojścia dla sąsiada > waga dojścia do wierzchołka + waga między		     	wierzchołkiem i sąsiadem
          then		
          begin
	  dla sąsiada waga dojścia := waga dojścia do wierzchołka + waga między 	 			wierzchołkiem i sąsiadem;
	  dla sąsiada wierzchołek poprzedni := wierzchołek;
          end
       end
    end   
until wszystkieWierzchołkiOdwiedzone;
od wybranego wierzchołka końcowego odczytuj wierzchołki poprzednie i rysuj rozwiązanie