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: 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 ] ) { 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 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 |
|
DejaVu |
» 2010-05-20 01:26:35 Wyszukiwanie jest zawsze z wierzchołka 0? /edit: W złym miejscu masz: 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. |
|
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: 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 ] ) { 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 ); } } } |
|
DejaVu |
» 2010-05-20 13:30:49 Porównaj sobie z tym: void dijkstra( int s ) { int v, u, c; waga.clear(); 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 ] ) { 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? |
|
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... |
|
DejaVu |
» 2010-05-20 14:43:59 Usuwasz j'ty wierzchołek, a potem ten sam wstawiasz... |
|
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? |
|
« 1 » |