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