Algorytm Dijkstry - 2 implementacje

Witam,

Mam pytanie dotyczące algorytmu Dijkstry. Zawsze używałem następującej implementacji w c++:

    struct edge //potrzebne tylko dla std::set poniżej
    {
        int vertex;
        unsigned long weight;

        edge(int v, unsigned long wt) : vertex(v), weight(wt) { }

        bool operator<(const edge& e2) const
        {
            return weight < e2.weight;
        }
    };

    void dijkstra_algorithm()
    {
        for(int i = 0 ; i < G.V() ; ++i)
        {
            wt[i] = ULONG_MAX;  //długość najkr. ścieżki od wierzchołka start. do i
            spt[i] = 0;         //ostatnia krawędź prowadząca do wierzchołka i
        }
        
        int v = start_vertex;
        wt[v] = 0;

        std::set<edge> vertex_queue;
        vertex_queue.insert(edge(v, wt[v]));

        while(!vertex_queue.empty())
        {
            v = vertex_queue.begin()->vertex;
            vertex_queue.erase(vertex_queue.begin());

            DenseWeightedGRAPH::adjIterator A(G, v);
            for(Weighted_edge* e = A.beg() ; !A.end() ; e = A.nxt())    //przetwarzamy każdego sąsiada
                //wierzchołka v, sąsiad jest zapisany jako klasa Weighted_edge
            {
                unsigned long P = wt[v] + e->wt();  //wt() zwraca wagę krawędzi
                int w = e->other(v);    //ta funkcja zwraca wierzchołek leżący naprzeciwko wierzchołka "v" w krawędzi "e"

                if(P < wt[w])
                {
                    vertex_queue.erase(edge(w, wt[w]));

                    wt[w] = P;
                    spt[w] = e;

                    vertex_queue.insert(edge(w, wt[w]));
                }
            }
        }
    }

Ale gdy odpaliłem jedno zadanie na pewnej sprawdzarce online, długo szukany problem tkwił w tym algorytmie, który raczej mnie nie zawodził. Powyższy program nie przechodził największego testu, więc ciężko było mi prześledzić jego działanie.

W necie znalazłem inną implementację Dijkstry i zmodyfikowałem ją pod moją implementację grafu:

void dijkstra_algorithm()
    {
        for(int i = 0 ; i < G.V() ; ++i)
        {
            wt[i] = ULONG_MAX;  
            spt[i] = 0;
        }

        int v = start_vertex;
        wt[v] = 0;

        bool visit[MAX_VERTICES] = { false };

        queue<int> q;
        q.push(v);
        while (!q.empty())
        {
            v = q.front();
            q.pop();
            visit[v] = false;

            DenseWeightedGRAPH::adjIterator A(G, v);
            for(Weighted_edge* e = A.beg() ; !A.end() ; e = A.nxt())
            {
                unsigned long P = wt[v] + e->wt();
                int w = e->other(v);

                if(P < wt[w])
                {
                    wt[w] = P;
                    spt[w] = e;

                    if(!visit[w])
                    {
                        visit[w] = true;
                        q.push(w);
                    }
                }
            }
        }
    }

Jak widać jest tam jakaś tablica odwiedzonych i kolejka zamiast kolejki priorytetowej w formie std::set.

Dzięki takiemu algorytmowi mój program przechodzi pewien duży test, ale dlaczego mój pierwszy algorytm nie działa? Ten drugi wydaje się być nawet prostszy, ale nigdy się nad takim nie zastanawiałem bo w definicji algorytmu Dijkstry zawsze pojawia się słowo "kolejka priorytetowa". Z wikipedii, jako jeden z kroków:

Utwórz kolejkę priorytetową Q wszystkich wierzchołków grafu. Priorytetem kolejki jest aktualnie wyliczona odległość od wierzchołka źródłowego s.

(Natomiast pierwszy algorytm wziąłem jakiś czas temu z http://rosettacode.org/wiki/Dijkstra's_algorithm#C.2B.2B i zmodyfikowałem pod moją implementację grafu - wydaje mi się że zrobiłem to dobrze zgodnie z definicją tego algorytmu.)

Czy w pierwszym algorytmie jest jakiekolwiek wąskie gardło?

Po pierwsze nie rozumiem tego DenseWeightedGRAPH::adjIterator A(G, v);, ale możliwe ze nie jest to jakoś bardzo istotne. Chyba najważniejszą różnicą jest to że set jest bardzo wolną strukturą danych, sprawdź to w ten sposób, że w drugim kodzie użyj seta zamiast tego queue, inną sprawą jest to, że wedle mnie Queue nie powinno działać. W końcu przecież chodzi nam o to aby za każdym razem wyciągać wierzchołek o najmniejszym koszcie a w Queue tego się nie uwzględnia, tam powinno być priority_queue. (w sumie podanie kontrprzykładu jest jakieś robialne, ktoś się wypowie? )

Nie jestem pewien czy przejście ostatniego testu jest sprawą akurat dijkstry, jesli zadanie polega również na kilku innych krokach to je sprawdź, bo ciężko mi uwierzyć, że set i robienie tego na strucktach jest aż o tyle wolniejsze :)

EDIT:

Jesli odpowiednio wpisze się dane to Twój program dla takiego grafu (gdzie zakładamy że zacznie od góry a tam jest najdrożej i mamy n(n-1)/2 krawędzi) wykona około n**2/2 operacji , co jest pesymistycznie gorsze od zakładanego pesymistycznego przypadku w dobrze zakodzonej Dijkstrze :)
(od źródła wychodzi n-2 wierzchołków , taki duży graf trzy poziomowy)

rjiuk napisał(a):

Nie jestem pewien czy przejście ostatniego testu jest sprawą akurat dijkstry, jesli zadanie polega również na kilku innych krokach to je sprawdź, bo ciężko mi uwierzyć, że set i robienie tego na strucktach jest aż o tyle wolniejsze :)

Błąd polega na podawaniu złej odpowiedzi. Program sprowadza się do dodawania dwóch najkrótszych ścieżek w dwóch grafach ale i tak problem leży tylko w tym algorytmie - jeśli zmienię go na mój pierwszy to jest podawana błędna odpowiedź.

Czyli rozumiem, że mój pierwszy algorytm sam w sobie nie jest zły?

Musisz pisać co oznacza "nie przechodzi", myślałem że chodziło Ci o czas wykonywania.

Wedle mnie Twój algorytm jest okej, czy kiedy zamienisz te dwie funkcje to jest ok ? Może jakieś tablice są za małe, no bo to dziwne że przechodzi Ci wszystkie testy oprócz jakiegoś dużego, najczęstszym problemem jest rozmiar a nie algorytm, posprawdzaj tablice ew czy limit pamięci czy coś :)

rjiuk napisał(a):

Wedle mnie Twój algorytm jest okej, czy kiedy zamienisz te dwie funkcje to jest ok ?

Jak zmienię drugą na pierwszą to podaje złą odpowiedź, z pamięcią i czasem działania jest wszystko OK - zła jest tylko odpowiedź...

Okazało się, że zamiast mojej struktury edge, którą inicjalizowałem std::set trzeba było użyć pair:

int v = start_vertex;
        wt[v] = 0;

        std::set<pair<unsigned long, int>> vertex_queue;
        vertex_queue.insert(make_pair(wt[v], v));

        while(!vertex_queue.empty())
        {
            v = vertex_queue.begin()->second;
            vertex_queue.erase(vertex_queue.begin());

            DenseWeightedGRAPH::adjIterator A(G, v);
            for(Weighted_edge* e = A.beg() ; !A.end() ; e = A.nxt())    //przetwarzamy każdego sąsiada
                //wierzchołka v, sąsiad jest zapisany jako klasa Weighted_edge
            {
                unsigned long P = wt[v] + e->wt();  //wt() zwraca wagę krawędzi
                int w = e->other(v);    //ta funkcja zwraca wierzchołek leżący naprzeciwko wierzchołka "v" w krawędzi "e"

                if(P < wt[w])
                {
                    vertex_queue.erase(make_pair(wt[w], w));

                    wt[w] = P;
                    spt[w] = e;

                    vertex_queue.insert(make_pair(wt[w], w));
                }
            }
        }

Pair ma operator< który bierze pod uwagę oba składniki - u mnie i nr wierzchołka i wagę (wagę w pierwszej kolejności). Pytanie więc czemu przy takich samych najmniejszych wagach trzeba zdejmować tą która prowadzi do wierzchołka o mniejszym numerze - definicje na wikipedii tego nie uwzględniają...

Znowu się trochę zapędziłem. Oto nowa strukture edge, dzięki której program działa. Zmodyfikowałem operator< żeby działał tak jak dla pair:

     struct edge //potrzebne tylko dla std::set poniżej
    {
        int vertex;
        unsigned long weight;

        edge(int v, unsigned long wt) : vertex(v), weight(wt) { }

        bool operator<(const edge& e2) const
        {
            //return weight < e2.weight;
            return weight < e2.weight || ((e2.weight >= weight) && vertex < e2.vertex);
        }
    };

Ale przecież on zwraca true nawet jeśli e2.weight >= weight byle by tylko vertex < e2.vertex. A przecież numery wierzchołków nie grają roli w algorytmie dijkstry! Jakim cudem ten program działa?