Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

problem z alogrytem Dijkstry

Ostatnio zmodyfikowano 2010-05-22 16:54
Autor Wiadomość
klarkid
Temat założony przez niniejszego użytkownika
problem z alogrytem Dijkstry
» 2010-05-20 00:41:27
czesc!
mam pewien problem z moim alogrytmem i juz nie potrafie spojrzec na niego swiezym okiem, gdyz czasem wychodza bledne wyniki, tzn wszystko zalezy od wygnerowanego losowo grafu (wyniki porownuje z algorytmem bellmana-forda, ktory jest prawidlowy). Graf przechowuje w macierzy wag nxn (reprezentuje go tablica **tab), jest on skierowany. nieskoczonosc jest rowna 1000. oto moj kod:
C/C++
int * dijkstra() {
    int i, j;
   
    set < prior, prior_porownaj > kopiec1;
    set < prior, prior_porownaj >::iterator it = kopiec1.begin();
   
    int * tablica = new int[ liczbawierzcholkow ];
    prior temp, pomoc;
   
    kopiec1.clear();
   
    for( i = 0; i < liczbawierzcholkow; i++ ) {
        tablica[ i ] = 1000;
    }
    tablica[ 0 ] = 0;
    temp.priorytet = 0;
    temp.wierzcholek = 0;
    kopiec1.insert( temp );
    for( i = 1; i < liczbawierzcholkow; i++ ) {
        temp.priorytet = tab[ 0 ][ i ];
        temp.wierzcholek = i;
        kopiec1.insert( temp );
    }
   
   
    while( !kopiec1.empty() ) {
       
        it = kopiec1.begin();
        temp =*( kopiec1.begin() );
        for( j = 0; j < liczbawierzcholkow; j++ ) {
           
            if( tablica[ j ] > tablica[ temp.wierzcholek ] + tab[ temp.wierzcholek ][ j ] ) { //relaksacja
                tablica[ j ] = tablica[ temp.wierzcholek ] + tab[ temp.wierzcholek ][ j ];
               
                for( it = kopiec1.begin(); it != kopiec1.end(); it++ ) {
                    if( it->wierzcholek == j ) {
                        kopiec1.erase( it );
                        it = kopiec1.begin();
                    }
                }
                pomoc.priorytet = tablica[ j ];
                pomoc.wierzcholek = j;
                kopiec1.insert( pomoc );
               
            }
           
        }
        kopiec1.erase( kopiec1.begin() );
    }
   
    return tablica;
   
}
 gdzie
C/C++
struct prior {
    int priorytet, wierzcholek;
   
};

struct prior_porownaj {
    bool operator ()( const prior & priorytet1, const prior & priorytet2 )
    {
        if( priorytet1.priorytet < priorytet2.priorytet ) return true;
       
        if( priorytet1.priorytet > priorytet2.priorytet ) return false;
       
        return false;
    }
};
nie potrafie wylapac tu bledu :( moze ktos z Was widzi co robie zle? Ps. jest to moj 1 post mam nadzieje ze uzylem dobrych tagow. pozdr
P-17030
DejaVu
» 2010-05-20 01:26:35
Wyszukiwanie jest zawsze z wierzchołka 0?

/edit:
W złym miejscu masz:
C/C++
kopiec1.erase( kopiec1.begin() );
Do kopca może zostać wstawiony element mniejszy niż ten, który był przy wejściu w pętlę, więc w konsekwencji skasujesz nie ten wierzchołek co trzeba, a dalej to chyba już nie trzeba pisać na temat konsekwencji.
P-17031
klarkid
Temat założony przez niniejszego użytkownika
» 2010-05-20 13:08:58
tak, tak, zawsze startuje od 0 wierzcholka, takie bylo zalozenie. hmm, zmienilem w ten sposob, ale wciaz bez dobrego efektu:
C/C++
while( !kopiec1.empty() ) {
   
   
    temp =*( kopiec1.begin() );
    kopiec1.erase( kopiec1.begin() );
    it = kopiec1.begin();
    for( j = 0; j < liczbawierzcholkow; j++ ) {
       
        if( tablica[ j ] > tablica[ temp.wierzcholek ] + tab[ temp.wierzcholek ][ j ] ) { //relaksacja
            tablica[ j ] = tablica[ temp.wierzcholek ] + tab[ temp.wierzcholek ][ j ];
           
            //uaktualnic.
            for( it = kopiec1.begin(); it != kopiec1.end(); it++ ) {
                if( it->wierzcholek == j ) {
                   
                    kopiec1.erase( it );
                    it = kopiec1.begin();
                   
                }
            }
            pomoc.priorytet = tablica[ j ];
            pomoc.wierzcholek = j;
            kopiec1.insert( pomoc );
           
        }
       
    }
    //kopiec1.erase(kopiec1.begin());
}
P-17033
DejaVu
» 2010-05-20 13:30:49
Porównaj sobie z tym:
C/C++
void dijkstra( int s )
{
    int v, u, c;
    waga.clear(); // kasuje wektor
    waga.resize( n, infty ); //
   
    waga[ s ] = 0;
    kopiec.clear();
    for( int i = 0; i < n; i++ ) kopiec.insert( i );
   
    while( !kopiec.empty() )
    {
        u = *( kopiec.begin() );
        kopiec.erase( kopiec.begin() );
       
        for( int i = 0; i < adj[ u ].size(); i++ )
        {
            v = adj[ u ][ i ].first;
            c = adj[ u ][ i ].second;
            if( waga[ u ] + c < waga[ v ] )
            {
                // uaktualniamy wagę wierzchołka v
                kopiec.erase( kopiec.find( v ) );
                waga[ v ] = waga[ u ] + c;
                kopiec.insert( v );
            }
        }
    }
   
   
}
Źródło: http://www.rafalnowak.pl/wiki/index.php?title=Algorytm_Dijkstry

/edit:
A tak swoją drogą to po co używać std::set'a skoro wyszukujesz w nim wartości liniowo?
P-17034
klarkid
Temat założony przez niniejszego użytkownika
» 2010-05-20 13:40:16
hm, wiec jest calkiem podobnie, kasowanie gory kopca dzieje sie w tym samym momencie.
edit:
na poczatku chcialem wykorzystac procedure find, ale nie wiem w jaki spoosb to zrobic, tak zeby szukalo wierzcholkow. i ktos mi powiedzial, ze mozna tylko zrobic to liniowo, za pomoca iteratorow. to moje pierwsze spotkanie z STL, prosze o wyrozumialosc :) bardziej martwie sie tym, ze algorytm nie dziala...
P-17035
DejaVu
» 2010-05-20 14:43:59
Usuwasz j'ty wierzchołek, a potem ten sam wstawiasz...
P-17036
klarkid
Temat założony przez niniejszego użytkownika
» 2010-05-22 16:54:08
no tak, z uaktualniona odlegoscia. a gdzie powinienem go wstawic?
P-17084
« 1 »
  Strona 1 z 1