Wątek przeniesiony 2018-02-13 12:50 z Newbie przez somekind. Powód: Próba uzyskania gotowca

Schemat blokowy

Odpowiedz Nowy wątek
2018-02-13 12:26
0

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

        }
    }
}

Dziękuję:)

Pokaż, co już sam zrobiłeś, lub załóż wątek w dziale Ogłoszenia drobne. Na tym forum pomagamy, a nie odwalamy czyjąś robotę. - Patryk27 2018-02-13 12:29

Pozostało 580 znaków

2018-02-13 12:30
2

A ja potrzebuję zimnego piwka na wieczór :).

Kolego, to nie koncert życzeń. Schematu blokowego do tego konkretnego kodu nie ma, lub nie znajdziesz go, więc jedyne co pozostaje to go narysować. Jeżeli liczysz że ktoś poświęci z 2 godziny żeby go przeczytać i przerysować to muszę Cię rozczarować. W teorii albo zrobisz to sam, a nas spytasz o konkretny problem, albo dasz to do ogłoszeń drobnych. W praktyce zostaje tylko pierwsza opcja bo nie wolno tam zamieszczać ogłoszeń na zaliczenie, a to ewidentnie takie jest.

Także program w dłoń, czytasz i rysuj.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0