Algorytm Dijkstry (w trakcie pisania)

Wyszukiwanie najkrótszej drogi między parą wierzchołków w grafie

Algorytm Floyda-Warshalla w przeciwieństwie do algorytmu Dijkstry można było zastosować w grafach z ujemnymi wagami krawędzi, warunkiem było aby w grafie nie występowały ujemne pętle.

Algorytm Dijkstry jest algorytmem zachłannym czyli w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, najlepiej rokującego w danej chwili rozwiązania częściowego. Podczas pracy algorytmu nie jest dokonywana ocena odnośnie całokształtu jedynie ocena lokalna i wybierane jest rozwiązanie lokalnie optymalne.

Przykładowe zastosowanie algorytmu Dijkstry

Algorytm ten może być wykorzystywany przy obliczaniu najkrótszej drogi na mapie zakładając, że każde skrzyżowanie to wierzchołek a odległości między nimi to wagi. Również jest wykorzystywany przy trasowaniu w sieciach komputerowych w protokole OSPF (wiki).

Działanie algorytmu

Algorytm polega na wybieraniu drogi, która w danej chwili ma najniższy koszt. Startując z wierzchołka s szukamy wagi która jest najniższa i przechodzimy do wierzchołka po tej krawędzi.

Algorytm ten również ma złożoność O(n2) zaś Floyda-Warshalla O(n3). Również jego zaletą jest to, że nie są obliczane wszystkie odległości tylko wyszukiwana ta do celu, dzięki czemu może algorytm zakończyć się wcześniej, co nie ma miejsca w Floydzie-Warshallu. Również tam gdzie graf się zmienia warto rozważyć ten algorytm, przy niezmiennych Floyd-Warshall.

Implementacja kodu

Do testowania implementacji zastosujemy ten sam graf co w algorytmie Floyda-Warshalla:

Ryc. 1. Graf do testowania implementacji kodu
Ryc. 2. Macierz sąsiedztwa grafu z Ryc. 1.
using System;

namespace Dijkstra
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Przykładowa implementacja algorytmu Dijkstry");

            //przygotowanie danych
            //utworzenie tablicy
            int rozmiar_tablicy = 5; //ilosc wierzchołków grafu
            var tablica = new int[rozmiar_tablicy, rozmiar_tablicy];

            //wypełnienie tablicy

            for (int i = 0; i < rozmiar_tablicy; i++)
                for (int j = 0; j < rozmiar_tablicy; j++)
                {
                    tablica[i, j] = Dijkstra.INFINITI;
                }

            //uzupełnienie macierzy sąsiedztwa
            //tablica zaharkodowana, najlepiej by było przekazywać macierz jako parametr
            tablica[0, 1] = 2;
            tablica[0, 2] = 3;
            tablica[1, 3] = 3;
            tablica[1, 4] = 7;
            tablica[2, 3] = 4;
            tablica[3, 4] = 1;

            //utworzenie instancji klasy
            var dijkstra = new Dijkstra(tablica);

            //pobranie ścieżki między wierzchołkami podanymi w parametrze metody
            var test = dijkstra.GetPath(0, 4);

            foreach (var item in test)
            {
                Console.WriteLine(item.ToString());
            };

            Console.ReadLine();
        }

        class Dijkstra
        {
            //stała - nieskończoność
            public const int INFINITI = int.MaxValue;
            public int[,] Tablica { get; set; }
            public Dijkstra(int[,] tablica)
            {
                Tablica = tablica;
            }


            public int[] GetPath(int start, int meta)
            {
                int rozmiarTablicy = Tablica.GetLength(0);
                int[] odleglosc = new int[rozmiarTablicy];
                int[] poprzednik = new int[rozmiarTablicy];
                int[] wezel = new int[rozmiarTablicy];

                for (int i = 0; i < odleglosc.Length; i++)
                {
                    odleglosc[i] = poprzednik[i] = INFINITI;
                    wezel[i] = i;
                }

                odleglosc[start] = 0;

                do
                {
                    int najmniejszy = wezel[0];
                    int najmniejszyIndex = 0;
                    for (int i = 0; i < rozmiarTablicy; i++)
                    {
                        if (odleglosc[wezel[i]] < odleglosc[najmniejszy])
                        {
                            najmniejszy = wezel[i];
                            najmniejszyIndex = i;
                        }
                    }

                    rozmiarTablicy--;
                    wezel[najmniejszyIndex] = wezel[rozmiarTablicy];

                    if (odleglosc[najmniejszy] == INFINITI || najmniejszy == meta)
                    {
                        break;
                    }

                    for (int i = 0; i < rozmiarTablicy; i++)
                    {
                        int j = wezel[i];
                        int nowaOdleglosc = odleglosc[najmniejszy] + Tablica[najmniejszy, j];
                        if (nowaOdleglosc < odleglosc[j])
                        {
                            odleglosc[j] = nowaOdleglosc;
                            poprzednik[j] = najmniejszy;
                        }
                    }
                }
                while (rozmiarTablicy > 0);

                return RekonstruktorSciezki(poprzednik, start, meta);
            }

            public int[] RekonstruktorSciezki(int[] prev, int start, int meta)
            {

                int[] ret = new int[prev.Length];
                int currentNode = 0;
                ret[currentNode] = meta;
                while (ret[currentNode] != INFINITI && ret[currentNode] != start)
                {
                    ret[currentNode + 1] = prev[ret[currentNode]];
                    currentNode++;
                }
                if (ret[currentNode] != start)
                    return null;
                int[] reversed = new int[currentNode + 1];
                for (int i = currentNode; i >= 0; i--)
                    reversed[currentNode - i] = ret[i];
                return reversed;
            }
        }
    }
}

Algorytm Floyda-Warshalla (w trakcie pisania)

Wyszukiwanie najkrótszej drogi między parą wierzchołków w grafie

Problem

Aby znaleźć drogę do celu musimy drogę zaplanować. Możemy wyszukać najszybszą, najtańszą, ekonomiczną. A jak sprawdzić która to która? Mamy wiele algorytmów pomagających nam to obliczyć i jednym z nich jest algorytm Floyda-Warshalla. Algorytm ten pozwala odnaleźć najkrótszą drogę między dwoma wierzchołkami w grafie ważonym.

Jak działa algorytm?

W grafie jeżeli najkrótsza droga między wierzchołkami a i c prowadzi przez wierzchołek b to znaczy, że jest ona połączeniem najkrótszych dróg między a i b oraz b i c.

Na początku algorytmu definiowana jest tablica najkrótszych ścieżek, tak że dla każdej pary wierzchołków mamy:

  • 0 gdy a = c (ten sam wierzchołek)
  • w(a, c) gdy istnieje krawędź między a i c
  • nieskończoność gdy nie istnieje krawędź między a i c

Złożoność algorytmu

Implementacja algorytmu

Sposobem przechowywania grafu w pamięci komputera są różne struktury danych. Jedną z nich jest macierz. Za pomocą macierzy możemy opisać które wierzchołki sąsiadują z innymi.

Przykładowa macierz może wyglądać następująco:

Ryc. 1. Macierz sąsiedztwa dla grafu z ryc. 2

A graf który przedstawia to:

Ryc. 2. Przykładowy graf nieskierowany

Do opisu grafów ważonych wykorzystuje się również macierz wag.

Ryc. 3. Macierz wag dla grafu z ryc. 4.

W implementacji wykorzystamy graf opisany macierzą:

Ryc.5. Macierz sąsiedztwa grafu wykorzystanego w implementacji kodu.

Graf będzie się przedstawiał następująco:

Ryc. 6. Graf wykorzystany w przykładowej implementacji kodu.
using System;
using System.Collections.Generic;

namespace FloydWarshall
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Przykładowa implementacja algorytmu Floyda-Warshalla");

            //przygotowanie danych
            //utworzenie tablicy
            int rozmiar_tablicy = 5; //ilosc wierzchołków grafu
            var tablica = new int[rozmiar_tablicy, rozmiar_tablicy];

            //wypełnienie tablicy

            for (int i = 0; i < rozmiar_tablicy; i++)
                for (int j = 0; j < rozmiar_tablicy; j++)
                {
                    tablica[i, j] = Floyd.INFINITI;
                }

            //uzupełnienie macierzy sąsiedztwa
            //tablica zaharkodowana, najlepiej by było przekazywać macierz jako parametr
            tablica[0, 1] = 2;
            tablica[0, 2] = 3;
            tablica[1, 3] = 3;
            tablica[1, 4] = 7;
            tablica[2, 3] = 4;
            tablica[3, 4] = 1;

            //utworzenie instancji klasy
            var floyd = new Floyd();
            //wyliczenie odległości między wierzchołkami
            floyd.Evaluate(rozmiar_tablicy, tablica);

            //pobranie ścieżki między wierzchołkami podanymi w parametrze metody
            var test = floyd.GetPath(0, 4);

            foreach (var item in test)
            {
                Console.WriteLine(item.ToString());
            };

            Console.ReadLine();
        }
    }

    class Floyd
    {
        //stała - nieskończoność
        public const int INFINITI = int.MaxValue;

        //tymczasowa zmienna, podczas iteracji przechowuje wartosc obliczaną wg algorytmu
        int[,] nastepnik;

        //ścieżka 
        int[,] sciezka;

        //wyliczenie odległości między wierzchołkami w grafie
        public void Evaluate(int rozmiar_tablicy, int[,] sciezka)
        {
            this.sciezka = sciezka;
            nastepnik = new int[rozmiar_tablicy, rozmiar_tablicy];
            for (int i = 0; i < rozmiar_tablicy; i++)
                for (int j = 0; j < rozmiar_tablicy; j++)
                    if (sciezka[i, j] == INFINITI)
                        nastepnik[i, j] = INFINITI;
                    else
                        nastepnik[i, j] = i;
            for (int k = 0; k < rozmiar_tablicy; k++)
                for (int i = 0; i < rozmiar_tablicy; i++)
                    for (int j = 0; j < rozmiar_tablicy; j++)
                        if (sciezka[i, k] != INFINITI && sciezka[k, j] != INFINITI &&
                sciezka[i, k] + sciezka[k, j] < sciezka[i, j])
                        {
                            sciezka[i, j] = sciezka[i, k] + sciezka[k, j];
                            nastepnik[i, j] = k;
                        }

            //sprawdzenie czy nie ma ujemnych ścieżek
            for (int i = 0; i < rozmiar_tablicy; i++)
                if (sciezka[i, i] < 0)
                    throw new ArgumentException("Negative cycles");
        }

        //pobranie najkrótszej ścieżki 
        public List<int> GetPath(int start, int meta)
        {
            var path = new List<int>();

            if (nastepnik == null)
                return null;
            if (nastepnik[start, meta] == INFINITI)
                return new List<int>();
            if (start == meta)
                return new List<int>() { start };
            getPathRekonstruktor(path, start, meta);
            path.Add(meta);

            return path;
        }

        //metoda rekursywna do pobierania ścieżki między węzłami
        private void getPathRekonstruktor(List<int> sciezka, int start, int meta)
        {
            int posredni = nastepnik[start, meta];
            if (posredni == start)
            {
                sciezka.Add(start);
                return;
            }
            getPathRekonstruktor(sciezka, start, posredni);
            getPathRekonstruktor(sciezka, posredni, meta);
        }
    }
}

Ulubione podkasty w 2019 roku

Podkasty są to nagrania (audio lub video), które możemy słuchać sprzedawców, pasjonatów, magików i świrów. Podkast wyróżnia się tym, że zastosowany jest tutaj kanał RSS.

Jeśli nie wiesz jak słuchać to link z podstawami tutaj: klik! . Prezentuje tam co prawda tylko jeden program i to na Androida ale znalezienie innych nie powinno sprawić Ci problemów.

Sam aktualnie korzystam z aplikacji PocketCast z której jestem bardzo zadowolony i którą również polecam, ponieważ ma klienta na iOS, Android i Windows a urządzenia mogą się między sobą synchronizować.

Część z podkasterów sprzedaje różne produkty a część po prostu dzieli się swoją pasją. Nie ważne czy trafimy na pierwszego czy na drugiego to zawsze otrzymamy coś ciekawego:

  • darmową wiedzę (którą można uzupełnić tą płatną oferowaną właśnie przez podkastera) – czasem będzie więcej a czasem mniej;
  • poznanie pasji innych ludzi;
  • miłe spędzenia czasu podczas czynności których nie lubimy: pranie, gotowanie, prasowanie;
  • jeszcze milsze spędzenie czasu który i tak nam sprawia przyjemność: jazda samochodem, jazda rowerem, bieganie 🙂
  • i wiele innych…

Moje słuchanie zaczęło się od audiobooków właśnie za kierownicą a później do tego doszły podkasty.

Bez Montażu, Bez Cenzury (RSS)

Nie wiem w sumie o czym to jest, bardzo miło się tego słucha bo jest o wszystkim. Polecam ponieważ trafiłem tam na grupę ludzi z którymi można się powymieniać doświadczeniami, opiniami, pożartować a czasem razem pomilczeć 🙂 Jeśli ktoś chciałby dołączyć to zapraszam również. Link poznacie po przesłuchaniu 🙂

Podkaster ten stwierdził, że kończy nadawanie tutaj i wraca do filmów na YT ale podejrzewam, że szybko mu się to zmieni 😉

Imagined Life (RSS)

W języku angielskim: 45 min przyjemnie zrobionego podkastu o kimś kogo zapewne znasz, może podziwiasz albo przeciwnie. Ale dopiero na końcu się dowiesz o kim to było. Ciekawa koncepcja, przyjemna realizacja.

Kontestacja (RSS)

Trochę polityki, podsumowań tego co się dzieje na świecie a także wiele innych ponieważ udostępniają również wiele innych podkastów.

Kryminatorium (RSS)

Nocą boisz się wyjść z domu bo możesz zostać napadnięty? Posłuchaj a będziesz się bał jeszcze bardziej 🙂

Książki które uczą (RSS)

Wszystko co w tytule.

Mała Wielka Firma (RSS)

Jeden z pierwszych podkastów jakie miałem okazję słuchać a słucham do dziś. Dużo wiedzy dla przedsiębiorców.

Na podsłuchu – Niebezpiecznik.pl (RSS)

W sieci czyha na nas wiele niebezpieczeństw. Ekipa Niebezpiecznika jest zawsze na bieżąco i dlatego warto ich słuchać. Większość ataków jest skuteczna ze względu na najsłabszy czynnik czyli nas samych. Wiedza pozwala nam się zabezpieczyć.

Na Sofie

Dużo przyjemnej muzyki “po której spróbujemy być dla siebie mili.”

Nerdy Nocą (RSS)

Historia, gorzelnictwo, zwiedzanie Stanów Mało Zjednoczonych Azji: Kurdystan, Afganistan, Pakistan i inne. Tematów nie brakuje a jakość materiałów na wysokim poziomie.

Otwieracz (RSS)

Masz pustkę w głowie i chcesz nad czymś porozkminiać? Odpal Otwieracz i będziesz miał tematy.

Podcast RADIOaktywny (RSS)

Dziewczyna ma pojęcie o reportażach, tematy różne, przyjemnie się słucha. Polecam

Pogaducha (RSS)

O życiu, o wszystkim. Tak na rozluźnienie

Stacja Zmiana

Trochę przemyśleń nad życiem, jak być lepszym człowiekiem.

Chaszcze and Thuja Haters (RSS)

Trochę prepperingu, podróży, przygotowań na trudne czasy, gadania o bzdurach. Się polecam 🙂

Po wachcie pod masztem (RSS)

I jeszcze jeden podkast, którego jestem uczestnikiem/autorem. Tym razem żeglarstwo.

Są to według mnie najciekawsze podkasty z tych które miałem okazję słuchać. Na liście mam ich oczywiście zdecydowanie więcej i wszystkie chętnie bym polecił ale jest ich ponad 300 i sam słucham tylko wybrane na podstawie tytułu odcinka. Jeżeli mnie zainteresuje to zaczynam, jeśli nie to archiwizuje i lecę dalej.

Ciebie również zachęcam do słuchania.

Wrzuć również w komentarzu co sam polecasz, chętnie sprawdzę.

Co warto przeczytać? Moje podsumowanie 2019r

Steve Jobs – Walter Isaacson

Przyjemna biografia świra i fanatyka, dlaczego Apple wygląda tak a nie inaczej, dlaczego produkty tej marki są tak chętnie kupowane. Co kierowało ludźmi, którzy właśnie te produkty tworzyli. A także kto…

Jony Ive – Leander Kaheny

“To przykre i frustrujące, że otaczają nas produkty, które zdają się świadczyć o całkowitym braku troski i staranności ze strony ich twórców. Przedmioty mają pewną bardzo ciekawą własność: nawet jeden potrafi powiedzieć mnóstwo o firmie, która go wyprodukowała; o jej wartościach i priorytetach.”

Jony Ive, 2005

I to o tym właśnie opowiada ta książka. O pasji do tworzenia przedmiotów doskonałych.

Włam się do mózgu – Radek Kotarski

Trochę doskonalenia siebie samego. Znajdziemy w tej książce trochę sposobów na przyswajanie wiedzy. Nie jest to tylko proste przedstawienie sposobów uczenia się ale też dokładne wytłumaczenie dlaczego tak się dzieje wraz z przykładami.

Autor korzystając z rozwiązań przedstawionych właśnie w tej książce nauczył się języka szwedzkiego w kilka miesięcy w sposób wystarczający do swobodnego komunikowania się z mieszkańcami tego kraju.

Efekt Motyla – Kamil Cebulski

Nie jest to może jakiś literacki majstersztyk ale jest to książka, którą warto przeczytać już będąc nastolatkiem a później poprawić jeszcze kilka razy.

Nie tylko w tej książce bo również w wielu innych miejscach się dowiedziałem, że szukanie pracy i pieniędzy to dwie różne sprawy. Warto też skalować pracę jaka będzie realizowana dzięki nam (nie tylko przez nas) aby nie sprzedawać bezpośrednio swojego czasu bo szybko dojdziemy do szklanego sufitu powyżej którego już nie wyskoczymy.

Jak przestać się martwić i zacząć żyć Dale Carnegie

Na koniec pozostawiam właśnie to co było dla mnie bardzo ważne. Sama książka nie jest perłą literatury ale próbuje uświadamiać jak martwienie się potrafi ograniczać nasze życie.

Do tego dorzucam jeszcze podkasty (zestawienie już niedługo), których przesłuchałem na prawdę dużo. Większość z nich zawsze mi dorzuciło jakieś ziarenko piasku do tego jaki jestem, co wiem, jak myślę, ale najwięcej pokazały mi podkasty podobnie jak powyższa książka. Stres niszczy, stres zabija. Panowanie nad stresem, zarządzanie nim jest niesamowicie ważne. Może to nie jest panowanie, to jest panowanie nad sobą pomimo stresu. Jest to ważna umiejętność, którą trzeba sobie jak najszybciej przyswoić. Ale zanim się ją posiądzie to trzeba mieć o tym wiedzę. Ja nie miałem i przez to pokutuje moje zdrowie. Stres bardzo mocnym piętnem odbił się na mnie i do tej pory to czuje, już kilka lat. Systematyczna praca nad sobą, można to nawet nazwać leczeniem swojej duszy jest bardzo trudnym zajęciem. Nie jest niemożliwe, da się to zrealizować, ale jest to bardzo trudne.

Coś co mogę również polecić a co nie jest już typową książką to własny dziennik z tego roku. Co nam poszło, co nie poszło, co zrealizowaliśmy a czego nie. I dlaczego tak się stało. Na pewno łatwiej nam będzie być lepszym człowiekiem, bo chyba o to właśnie chodzi. Codziennie lepszy…

Czytaj jak najwięcej!

W ogóle warto czytać książki. Wszystkie. Każda książka przez nas przeczytana zostawi w nas coś dzięki czemu będziemy bogatsi. Czasem to będzie cały rozdział, zmiana naszego widzenia, postrzegania świata. Czasem to tylko jedno zdanie, jedno słowo. Niektóre nie wniosą nic nowego do naszego życia i takich chyba jest najwięcej, ale pozwolą nam wejść w świat bohatera i oderwać się od swojej rzeczywistości, zrelaksować się trochę, ruszyć wyobraźnię. A nawet jeśli wg nas nie warto było czytać tej książki to jednak przeczytanie jej, pozwoliło nam trochę odejść od tego świata wirtualnego, może uspokoiło nasze oczy, może…. a sam sobie dopisz co Ci to dało.

“Nie garb się bo tak Ci zostanie!”

Nie raz tak słyszałem takie zdanie w szkole. Na szczęście mi tak nie zostało. Chociaż coraz częściej plecy bolą. Ale nie każdy ma takie szczęście.

Okazuje się, że zła postawa w pracy, czy to siedząca czy stojąca ma negatywny wpływ na nasze zdrowie. Nie tylko, że tak nam zostanie. Oprócz tego może mieć to negatywny wpływ na to jak się czujemy. Bóle głowy lub pleców po kilku latach nieprawidłowej postawy to norma. I pewnie nie tylko ja się z nią zmagam.

Nasza postawa to podstawa wszystkiego co robimy!

Wszystkie ruchy jakie wykonujemy, wszystkie obciążenia jakim poddajemy nasze ciało są determinowane naszą postawą. Jeżeli postawa nie jest prawidłowa to organizm jest poddawany siłom, które negatywnie wpływają na zdrowie. A do tego jeszcze dochodzi grawitacja, która dokłada swoje.

Wygodny fotel to zło!

Korzystając z wygodnych foteli sprawiamy, że chce nam się siedzieć dłużej. A nasz organizm nie jest przystosowany do siedzenia. Poprzez długotrwałe siedzenie w wygodnym fotelu dezaktywujemy mięśnie brzucha które pracują w trakcie utrzymywania prawidłowej, wyprostowanej postawy. Z innymi mięśniami jest podobnie.

Gdy te są osłabione to inne muszą przejąć ich zadania przez co często muszą pracować ponad ich normę. Mogą się wtedy pojawiać również niepotrzebne bóle.

Oprócz bólu mogą to być dodatkowo:

  • podatność na kontuzje
  • pogorszona wentylacja
  • zwiększona czułość na ból
  • osłabienie stawów i więzadeł.

Sama postawa wpływa również na nasz stan psychiczny. Będąc wyprostowanymi lepiej się czujemy, jesteśmy pewniejsi siebie, jesteśmy postrzegani pozytywniej niż ci którzy się garbią, są skuleni.

Co robić?

Ćwiczyć, siedzieć prosto, dużo się ruszać, pracować na stojąco z dużą ilością ruchu. Pozwodzenia i zdrowia!