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:

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