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

DIJKSTRA - problem

Ostatnio zmodyfikowano 2012-01-03 21:13
Autor Wiadomość
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:
C/C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int * odleglosc, * color; //TABLICE Z KOLOREM I ODLEGLOSCIA
priority_queue < pair < int, int > > kopiec; //DEKLARUJE KOLEJKE WIESZCHOŁKÓW
vector < pair < int, int > >* pary; // TABLICA SASIEDZTWA
void DIJKSTRA( int a )
{
    int i, costam;
    kopiec.push( make_pair( 0, a ) ); //WRZUCAM PIERWSZA WARTOSC
    while( kopiec.empty() == false )
    {
        int u = kopiec.top().second; //W PIERWSZYM PRZYPADKU U = A
        color[ u ] = 2; //KOLORUJE JAKO PRZETWORZONY
        kopiec.pop(); //KASUJE NAJWIEKSZA WARTOSC
        for( i = 0; i < pary[ u ].size(); i++ )
        {
            int m = pary[ u ][ i ].first; //ZEBY WYGODNIEJ SIE ODWOŁYWAŁO
            int n = pary[ u ][ i ].second; //JAK POWYZEJ
            if( odleglosc[ m ] > odleglosc[ u ] + n )
            {
                odleglosc[ m ] = odleglosc[ u ] + n; //AKTUALIZACJA ODLEGŁOŚCI
            }
            n += odleglosc[ u ]; //PRZETWORZENIE N
            n *=- 1; //NA POTRZEBY KOLEJKI PRIORYTETOWEJ
            if( color[ m ] == 0 )
            {
                kopiec.push( make_pair( n, m ) ); //TUTAJ NIE WIEM WIEC DAJE ŻE WRZUCA TYLKO NOWY WIESZCHOLEK
            }
            color[ m ] = 1; //OZJNACZA TEN WIESZCHOLEK JAKO NIEPEWNA ODPOWIEDZ (TO TEŻ PEWNIE ŹLE)
        }
    }
}
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; //NIESKONCZONA ODLEGLOSC
        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 ); //WEJSCIE DO DRUGIEGO WIESZCHOLKA
    return 0;
}
Moze ktoś dać jakąś wskazówkę?
Pozdrawiam
P-46944
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 :)
P-47024
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ć.
C/C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int * odleglosc, * color, * poprzednik; //TABLICE Z KOLOREM I ODLEGLOSCIA
priority_queue < pair < int, int > > kopiec; //DEKLARUJE KOLEJKE WIESZCHOŁKÓW
vector < pair < int, int > >* pary; // TABLICA SASIEDZTWA
int z;
void DIJKSTRA( int a )
{
    int i, costam, v, x, u;
    odleglosc[ a ] = 0; //BO ODLEGŁOŚĆ Z KATOWIC DO KATOWIC WYNOSI 0
    kopiec.push( make_pair( 0, a ) ); //WRZUCAM PIERWSZA WARTOSC
    //PIERWSZYM PARAMETREM W KOPCU JEST ODLEGŁOŚĆ PONIEWAŻ JEST TO WARTOŚĆ PRIORYTETOWA
    //DRUGIM PARAMETREM JEST  NUMER INDEXU JEST TO PARAMETR POMOCNICZY
    while( kopiec.empty() == false )
    {
        u = kopiec.top().second; //JEST TO AKTUALNIE ROZPATRYWANY WIESZCHOŁEK
        kopiec.pop(); //KASUJEMY GO ,PONIEWAŻ JEŚLI TEGO NIE ZROBIMY PO WYJŚCIU PĘTLI PROGRAM BEDZIE W NIM SIEDZIAŁ DO KOŃCA ŚWIATA
        for( i = 0; i < pary[ u ].size(); i++ )
        {
            int m = pary[ u ][ i ].first; //INDEX WIESZCHOŁKA SASIADUJĄCEGO
            int n = pary[ u ][ i ].second; //ODLEGLOŚĆ TYCH WIESZCHOŁKÓW
            if( odleglosc[ m ] > odleglosc[ u ] + n )
            {
                odleglosc[ m ] = odleglosc[ u ] + n; //AKTUALIZACJA ODLEGŁOŚCI
                poprzednik[ m ] = u; //TERAZ KATOWICE SĄ POPRZEDNIKIEM MIKOŁOWA CZYLI SĄ BLIŻEJ NA TRASIE NP Z WARSZAWY
                kopiec.push( make_pair( odleglosc[ m ] *- 1, m ) ); //CZYLI TERAZ MAMY NAJKRÓTSZE ODLEGŁOŚCI DO PUNKTÓW W KOPCU
            }
        }
        do
        {
            v = kopiec.top().first *- 1; //ODLEGŁOŚĆ OD NAJBLIŻSZEGO WIESZCHOŁKA
            x = kopiec.top().second; //INDEX NAJBLISZEGO MIASTA NP. MIKOŁOWA
            if( odleglosc[ x ] != v )
            {
                kopiec.pop(); //CZYLI ŻE NIE OPŁACA SIE IŚĆ TĄ DROGĄ
            }
        } while( odleglosc[ x ] != v && kopiec.size() > 0 );
       
    }
}
void ZERUJ()
{
    int x;
    for( x = 0; x < z; x++ )
    {
        odleglosc[ x ] = 2147483647; //NIESKONCZONA ODLEGLOSC
        poprzednik[ x ] =- 1; //BO NIE ROBIŁY SIĘ DZIKIE RZECZY NP SPRAWDZANIE CZY WIESZCHOŁEK 1 NIE MOZE BYC PRZODKIEM ROZPATRYWANEGO
    }
}
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; //WCZYTUJEMY WIESZCHOŁEK POCZĄTKOWY
        r--; //OBOWIĄZKOWA DEKREMENTACJA BEZ TEGO PROGRAM SIE WYSYPIE
        t--;
        ZERUJ(); //BO CHYBA NIE CHCESZ LICZYĆ ODLEGŁOŚCI Z MIKOŁOWA DO KATOWIC SUMA Z BANKOKU DO BERLINA?
        DIJKSTRA( r ); //INICJUJEMY DIJKSTRE
        if( odleglosc[ t ] != 2147483647 )
        {
            cout << odleglosc[ t ] << endl;
        } else
        {
            cout << "INF" << endl;
        }
    }
    return 0;
}
P-47169
DejaVu
» 2012-01-03 21:13:42
Ok, to skoro problem rozwiązany to zamykam :)
P-47188
« 1 »
  Strona 1 z 1