Algorytm Dijkstry

Z RNO-Wiki
Wersja Rno (dyskusja | edycje) z dnia 07:25, 22 mar 2007
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)

Implementacja w C++

Poniżej zamieszczam szybką i łatwą implementację algorytmu Dijkstry w C++ przy użyciu biblioteki STL, a dokładniej potrzebny jest kopiec, który w tej implementacji został zrealizowany za pomocą struktury set:

    #include<iostream>
    #include<vector>
    #include<set>

    using namespace std;

    const int infty = 1000000000; // uwaga na limit
    int n,m;
    vector< pair<int,int> > adj[100000];

    vector<int> waga;

    struct cmp
    {
        // czy a jest mniejsze od b
        bool operator() (const int &a, const int &b)
        {
            if (waga[a] < waga[b]) return true;
            if (waga[a] > waga[b]) return false;
            return a<b;
        }
    };


    set<int, cmp> kopiec; // ;-)


    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);
                }
            }
        }
       
       
    }

    int main(void)
    {
        int a,b,c, s,t;
       
        cin >> n >> m;
        for (int i=0; i<m; i++)
        {
            cin >> a >> b >> c; // c = koszt krawędzi od a do b
            adj[a].push_back( pair<int,int>(b,c) );
        }
       
        cin >> s >> t; // s - źródło, t - wierzchołek, do którego najkrótszej odległości szukamy
       
        dijkstra(s); // alg. Dijkstry wypełni całą tablicę waga[..] najkrótszymi odległościami
        cout << waga[t];
        return 0;
    }

Lo 21:51, 23 sty 2007 (CET)

Osobiste