Algorytm Dijkstry

RNO-Wiki

Algorytm Dijkstry jest bardzo dobrze znanym algorytmem wyszukiwania najkrótszych odległości w grafie (nie) skierowanym (od) z jednego źródła. W internecie jest wiele dokumentacji na jego temat. Ja zechęcam, do przestudiowania mojego wykładu o grafach, który wygłosiłem podczas Majówki z informatyką. Wykład, a właściwie to slajdy dostępne są tutaj Grafika:MajowkaRNO graphs.pdf.

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

Rafał Nowak 20:24, 1 gru 2007 (CET)

Źródło: "http://www.rafalnowak.pl/wiki/index.php?title=Algorytm_Dijkstry"