gistfile1.txt

/*******************************************************************************
*                                                                              *
*    ALGORYTM DIJKSTRY wyznaczania najkrotszej sciezki od                      *
*    danego wierzcholka do wszystkich pozostalych w grafie skierowanym         *
*    o nieujemnych wagach                                                      *
*    algorytm.org                                                              *
*         (wersja zmodyfikowana przez "Sinus32" w celu                         *
*          przystosowania do standardu jêzyka C++)                             *
*                                                                              *
********************************************************************************/

#include <cstdlib>
#include <iostream>
#include <limits>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

class cWierzcholek
{
    public:
        // Wierzcholek
        int	V;
        
        // Odleglosc wierzcholka pierwszego do wierzcholka V
        int* Odl; // bedzie wskazywac na odpowiednia komorke D[i]
        
        // Przeciazamy operator mniejszosci dla klasy cWierzcholek 
        friend bool operator< (cWierzcholek const & p1, cWierzcholek const & p2)
            {return *(p1.Odl) > *(p2.Odl);}
};

class cGraf
{
    public:
        // Konstruktory
        // Konstruktor kopiuj¹cy jest potrzebny, wiêc go zadeklarowa³em,
        // ale w tym programie nie jest wykorzystywany, a mi nie chce siê
        // go definiowaæ ;]
        cGraf(): A(0), D(0), n(0) {}
        cGraf(cGraf const & ref);
        ~cGraf();
        
        // Metoda ³aduj¹ca dane
        void LadujDane(int const newn, int const * dane);
        
        // Metoda pobieraj¹ca wynik
        int * PobierzWynik(int & rn) {rn = n; return D;}
        
        // Wartosc, od ktorej przyjmujemy nieskonczonosc
        static int const nieskonczonosc;
        
    private:
        // Metoda dokonuj¹ca obliczeñ
        void Dijkstra();
        
        // Macierz przyleglosci, w indeksie (i,j) zawiera wartosci:
        // 0 dla i=j
        // nieskonczonosc jezeli nie istnieje krawedz (i,j)
        // K > 0 waga krawedzi (i,j)
        int ** A;
        
        // Wektor odleglosci od pierwszego wierzcholka do pozostalych,
        // poczatkowo zawiera pierwszy wiersz macierzy A
        int * D;
        
        // Liczba wierzcholkow grafu
        int	n;
};
int const cGraf::nieskonczonosc = numeric_limits<signed int>::max();

cGraf::~cGraf()
{
    // Sprz¹tanie po obiekcie
    if (A)
    {
        for (int i = 0; i < n; ++i)
            if (A[i]) delete A[i];
        delete A;
    }
    if (D) delete D;
}

void cGraf::LadujDane(int const newn, int const * dane)
{
    // Niszczenie ewentualnych poprzednich danych
    if (A)
    {
        for (int i = 0; i < n; ++i)
            if (A[i]) delete A[i];
        delete A;
    }
    if (D) delete D;
    
    // Rezerwacja pamiêci
    n = newn;
    A = new int* [newn];
    for (int i = 0; i < newn; ++i)
        A[i] = new int[newn];
    D = new int [newn];
    
    // £adowanie nowych danych
    for (int j = 0; j < newn; ++j)
        for (int i = 0; i < newn; ++i)
            A[j][i] = *dane++;
    
    // Uruchomienie algorytmu Dijkstry
    Dijkstra();
}

void cGraf::Dijkstra()
{    
    // Kolejka priorytetowa wierzcholkow, uporzadkowana wg klucza,
    // ktorym jest atrybut Odl klasy cWierzcholek
    vector<cWierzcholek> Q;
    cWierzcholek wierzcholek;
    
    // Lista nastepnikow
    vector<int> nastepniki;
    
    // Przyjmujemy, ze wyznaczamy odleglosci od pierwszego wierzcholka w macierzy A
    for (int i = 0; i < n; ++i)
    {
        // Poczatkowo wektor D zawiera pierwszy wiersz macierzy A
        D[i] = A[0][i];
        
        // Dodaj dane z macierzy do kolejki Q
        wierzcholek.V = i;
        wierzcholek.Odl = &D[i];
        Q.push_back(wierzcholek);
    }
    
    vector<cWierzcholek>::iterator it;
    // Tworzymy kopiec
    make_heap(Q.begin(), Q.end(), less<cWierzcholek>());
    
    // Usun pierwszy wierzcholek (odleglosc od pierwszego
    // wierzcholka do pierwszego wierzcholka wynosi 0)
    pop_heap(Q.begin(), Q.end());
    Q.pop_back();
    
    while (Q.empty() != true)
    {
        // Przywrocenie wlasnosci kopca
        make_heap(Q.begin(), Q.end(), less<cWierzcholek>());
        
        // Pobierz pierwszy wierzcholek z kolejki Q (ma on najmniejsza wartosc klucza)
        wierzcholek = Q[0];
        
        // Usun go z kolejki
        pop_heap(Q.begin(), Q.end());
        Q.pop_back();
        
        // Wyznacz liste jego nastepnikow
        nastepniki.clear();
        for (int i = 0; i < n; ++i)
            if ((A[wierzcholek.V][i] != cGraf::nieskonczonosc) && (A[wierzcholek.V][i] != 0))
                nastepniki.push_back(i);
    
        // Dokonaj relaksacji odleglosci od wierzcholka pierwszego do kazdego
        // nastepnika z tej listy
        for (int i = 0; i < nastepniki.size(); ++i)
            D[nastepniki[i]] =
                min(D[nastepniki[i]], D[wierzcholek.V] + A[wierzcholek.V][nastepniki[i]]);
    }
}

int main(void)
{
    // Przyk³adowe dane:
    // Macierz wzajemnych odleg³oœci wierzcho³ków od siebie
    // Na grafie 5-cio wierzcho³kowym
    // Wygl¹d tablicy: ('*' == nieskoñczonoœæ)
    // 0 10 * * 5
    // * 0 1 * 2
    // * * 0 4 *
    // 7 * 6 0 *
    // * 3 9 2 0
    int obrazgrafu[5][5] = {
        0, 10, cGraf::nieskonczonosc, cGraf::nieskonczonosc, 5,
        cGraf::nieskonczonosc, 0, 1, cGraf::nieskonczonosc, 2,
        cGraf::nieskonczonosc, cGraf::nieskonczonosc, 0, 4, cGraf::nieskonczonosc,
        7, cGraf::nieskonczonosc, 6, 0, cGraf::nieskonczonosc,
        cGraf::nieskonczonosc, 3, 9, 2, 0
        };
    
    cGraf Graf;
    int n;
    
    // Wczytujemy dane
    // Uwaga: obrazgrafu jest typu int[5][5], a funkcja przyjmuje argument
    // const int *, wiêc rzutujê wskaŸnik na tablicê dwuwymiarow¹ do
    // wskaŸnika na tablicê jednowymiarow¹. Mogê to zrobiæ, bo przy deklaracji
    // int obrazgrafu[5][5] wszystkie 25 komórek znalaz³o siê w jednym ci¹gu
    // i wygl¹da jak jedna tablica 25-cio elementowa.
    Graf.LadujDane(5, reinterpret_cast<int*>(obrazgrafu));
    
    // Pobranie wyniku
    int * Wynik = Graf.PobierzWynik(n);
    
    // Wypisz wektor Wynik zastepujac wartosc stalej nieskonczonosc znakiem *
    int k = cGraf::nieskonczonosc;
    for (int i = 0; i < n; ++i)
        if (Wynik[i] < k)
            cout << "D(" << i << ")=" << Wynik[i] << '\n';
        else
            cout << "D(" << i << ")=*\n";
    cout.flush();
    
    cin.get();
    
    return 0;
}