Algorytm Dijkstry

From Nasza Pasja - Programowanie

Algorytm służy do znajdowania najkrótszych ścieżek w grafie skierowanym.

Zapis w pseudokodzie

Dla grafu G, funkcji wagowej w i wierzchołka s, otrzymamy tablicę d[u] odległości każdego wierzchołka grafu od wierzchołka s.

W tym zapisie funkcja u := Wyjmij_Min(Q) poszukuje wierzchołka u w zbiorze Q, mającego najmniejszą wartość d[u]. Ten wierzchołek jest usuwany ze zbioru Q i zwracany przez funkcję.

Dijkstra(G,w,s):

dla każdego wierzchołka v w V[G] wykonaj
  d[v] = nieskończone
  poprzednik[v] = niezdefiniowane
d[s] = 0
S = zbiór pusty
Q = zbiór wszystkich wierzchołków
dopóki Q nie jest zbiorem pustym wykonaj
  u = Wyjmij_Min(Q)
  S = suma zbiorów S i {u}
  dla każdego wierzchołka v, który jest sąsiedni do u wykonaj
    jeżeli d[v] > d[u] + w(u,v) to
      d[v] = d[u] + w(u,v)
      poprzednik[v] = u

[edytuj]

Implemenacja w C++

Program pobiera dane ze standardowego wejścia i wypisuje je na standardowe wyjście

Wejście. Pierwszą informacją na wejściu powinny być dwie liczby:

e n

gdzie e - liczba wierzchołków i n - liczba krawędzi. Następnie powinno wystąpić n trójek liczb:

a b c

gdzie a - numer pierwszego wierzchołka, b - numer drugiego wierzołka, c odległość między nimi.

Wyjście. Program zwraca e liczb, gdzie e-ta liczba to najkrótsza ścieżka między wierzchołkiem o numerze 1 i wierchołkiem o numerze e

// Autor: comboy

#include <iostream.h>

long long int ODLEGLOSC_MAX = 1000000001;
int rozmiar;

class element
{
        public:
        int numer;
        int waga;
        element *nastepny;

        element(int numerek, int wagus)
        {
                numer = numerek;
                waga = wagus;
        }
};

class lista
{
        public:
        element *glowa;
        element *ogon;

        void dopisz(int numer, int waga);

        lista()
        {
                glowa = NULL;
                ogon = NULL;
        }
};

void lista::dopisz(int numer, int waga)
{

        element *nowy=new element(numer,waga);

        if (glowa==NULL)
        {
                glowa = ogon = nowy;
        } else
        {
                ogon->nastepny = nowy;
                ogon = nowy;
        }

}

class wierzcholek
{
        public:
        bool obliczony;
        lista polaczenia;
        int kop_nr;
};

class wezel
{
        public:
        long long int odleglosc;
        int graf_nr;
};

wierzcholek graf[100000];
wezel kopiec[100000];

void zamien_kop(int numer1, int numer2)
{
        wezel tmp;
        tmp = kopiec[numer1];
        kopiec[numer1] = kopiec[numer2];
        kopiec[numer2] = tmp;
        graf[kopiec[numer2].graf_nr].kop_nr = numer2;
        graf[kopiec[numer1].graf_nr].kop_nr = numer1;
}

void uporzadkuj_wezel(int numer)
{
        int lewy=numer*2;
        int prawy=numer*2+1;
        int min;

        if (lewy<=rozmiar && kopiec[lewy].odleglosc<kopiec[numer].odleglosc)
        {
                min = lewy;
        } else min = numer;
        if (prawy<=rozmiar && kopiec[prawy].odleglosc<kopiec[min].odleglosc) min = prawy;

        if (numer!=min)
        {
                zamien_kop(numer,min);
                uporzadkuj_wezel(min);
        }
}



int main()
{

        int n;
        int e;

        cin >> n >> e;

        int a;
        int b;
        int w;

        // Usypanie kopca

        for (int i=1; i<=n; i++)
        {
                graf[i].kop_nr = i;
                kopiec[i].graf_nr = i;
                kopiec[i].odleglosc = ODLEGLOSC_MAX;
        }

        // Wczytywanie danych

        for(int i=0; i<e; i++)
        {
                cin >> a >> b >> w;
                graf[a].polaczenia.dopisz(b,w);
        }

        rozmiar = n;
        kopiec[0].odleglosc = -1;
        kopiec[1].odleglosc = 0;



        while (rozmiar>0)
        {
                element *temp;
                if (graf[kopiec[1].graf_nr].polaczenia.glowa!=NULL)
                {
                        temp = graf[kopiec[1].graf_nr].polaczenia.glowa;
                        while (temp!=NULL)
                        {
                                if (kopiec[graf[temp->numer].kop_nr].odleglosc > (temp->waga + kopiec[1].odleglosc))
                                {
                                        kopiec[graf[temp->numer].kop_nr].odleglosc = temp->waga + kopiec[1].odleglosc;
                                        int i=graf[temp->numer].kop_nr;
                                        while (kopiec[int(i/2)].odleglosc > kopiec[i].odleglosc)
                                        {
                                                zamien_kop(int(i/2),i);
                                                i = i/2;
                                        } // i pojechal sobie do gory
                                }
                                temp = temp->nastepny;
                        }
                }
                // A teraz najlepsze: scinamy kopcowi korzen :]
                zamien_kop(1,rozmiar+1);
                uporzadkuj_wezel(1);
                rozmiar--;
        }


        for (int i=1; i<=n; i++)
        {
                if (kopiec[graf[i].kop_nr].odleglosc == 1000000001)
                {
                        cout << "NIE" << endl;
                } else
                {
                        cout << kopiec[graf[i].kop_nr].odleglosc << endl;
                }

        }


}