matoł115 Temat założony przez niniejszego użytkownika |
DIJKSTRA - problem » 2012-01-01 19:18:08 Witam! Przede wszystkim chce złożyć wszystkim życzenia z okazji nowego roku. A przy okazji mam problem z algorytmem Dijkstry. Mam go stworzyć przy pomocy kolejki priorytetowej. Pierwszą rzeczą jakiej nie wiem, to jakie wartości zawierać ma kolejka na starcie. Dalej nie wiem kiedy stwierdzić, że odpowiedź dla danego wieszchołka jest OK. Na razie mam taki kod: #include <iostream> #include <vector> #include <queue> using namespace std; int * odleglosc, * color; priority_queue < pair < int, int > > kopiec; vector < pair < int, int > >* pary; void DIJKSTRA( int a ) { int i, costam; kopiec.push( make_pair( 0, a ) ); while( kopiec.empty() == false ) { int u = kopiec.top().second; color[ u ] = 2; kopiec.pop(); for( i = 0; i < pary[ u ].size(); i++ ) { int m = pary[ u ][ i ].first; int n = pary[ u ][ i ].second; if( odleglosc[ m ] > odleglosc[ u ] + n ) { odleglosc[ m ] = odleglosc[ u ] + n; } n += odleglosc[ u ]; n *=- 1; if( color[ m ] == 0 ) { kopiec.push( make_pair( n, m ) ); } color[ m ] = 1; } } } int main() { int z, i, a, b, c, k; cin >> z; odleglosc = new int[ z ]; color = new int[ z ]; pary = new vector < pair < int, int > >[ z ]; for( i = 0; i < z; i++ ) { odleglosc[ i ] = 2147483647; color[ i ] = 0; } cin >> k; for( i = 0; i < k; i++ ) { cin >> a >> b >> c; a--; b--; pary[ a ].push_back( make_pair( b, c ) ); pary[ b ].push_back( make_pair( a, c ) ); } DIJKSTRA( 1 ); return 0; }
Moze ktoś dać jakąś wskazówkę? Pozdrawiam |
|
DejaVu |
» 2012-01-01 22:52:38 Ładnie opisałeś linijki, jednak polecam Ci przeanalizować kilkukrotnie algorytm Dijkstry i jeżeli nie znajdziesz błędu porównując swój kod do pseudokodu - napisać go od nowa. Cała sztuka polega na tym by umieć naprawiać błędy w kodzie, który się napisało bądź otrzymało do poprawienia. Jak inni za Ciebie będą algorytmy naprawiali to żaden programista z Ciebie nie będzie :) |
|
matoł115 Temat założony przez niniejszego użytkownika |
» 2012-01-03 20:05:02 Udało mi się napisać Dijkstre :D Wysłałem ja na test i przeszła na 100%. Zamieszczę tutaj kod (jeśli można). Jeżeli widzi ktoś jakieś błędy/niedoróbki to proszę pisać. #include <iostream> #include <vector> #include <queue> using namespace std; int * odleglosc, * color, * poprzednik; priority_queue < pair < int, int > > kopiec; vector < pair < int, int > >* pary; int z; void DIJKSTRA( int a ) { int i, costam, v, x, u; odleglosc[ a ] = 0; kopiec.push( make_pair( 0, a ) ); while( kopiec.empty() == false ) { u = kopiec.top().second; kopiec.pop(); for( i = 0; i < pary[ u ].size(); i++ ) { int m = pary[ u ][ i ].first; int n = pary[ u ][ i ].second; if( odleglosc[ m ] > odleglosc[ u ] + n ) { odleglosc[ m ] = odleglosc[ u ] + n; poprzednik[ m ] = u; kopiec.push( make_pair( odleglosc[ m ] *- 1, m ) ); } } do { v = kopiec.top().first *- 1; x = kopiec.top().second; if( odleglosc[ x ] != v ) { kopiec.pop(); } } while( odleglosc[ x ] != v && kopiec.size() > 0 ); } } void ZERUJ() { int x; for( x = 0; x < z; x++ ) { odleglosc[ x ] = 2147483647; poprzednik[ x ] =- 1; } } int main() { ios_base::sync_with_stdio( 0 ); int i, a, b, c, k, ilosc, r, t, j; cin >> z >> k; odleglosc = new int[ z ]; color = new int[ z ]; poprzednik = new int[ z ]; pary = new vector < pair < int, int > >[ z ]; for( i = 0; i < k; i++ ) { cin >> a >> b >> c; a--; b--; pary[ a ].push_back( make_pair( b, c ) ); pary[ b ].push_back( make_pair( a, c ) ); } cin >> ilosc; for( i = 0; i < ilosc; i++ ) { cin >> r >> t; r--; t--; ZERUJ(); DIJKSTRA( r ); if( odleglosc[ t ] != 2147483647 ) { cout << odleglosc[ t ] << endl; } else { cout << "INF" << endl; } } return 0; }
|
|
DejaVu |
» 2012-01-03 21:13:42 Ok, to skoro problem rozwiązany to zamykam :) |
|
« 1 » |