Algorytm Dijkstry

Z RNO-Wiki
(Różnice między wersjami)
(Implementacja w C++)
 
m (Implementacja w C++)
 
(Nie pokazano 10 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
 +
[[Kategoria:Algorytmy grafowe]]
 +
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ówka z Informatyką|Majówki z informatyką]]. Wykład, a właściwie to slajdy dostępne są tutaj [[Grafika:MajowkaRNO graphs.pdf]].
 +
 
== Implementacja w C++ ==
 
== 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|'''set''']]:
 
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|'''set''']]:
<pre>
+
<table width="100%">
    #include<iostream>
+
<tr>
    #include<vector>
+
<td valign="top">
    #include<set>
+
<source lang="cpp">
 +
#include<iostream>
 +
#include<vector>
 +
#include<set>
  
    using namespace std;
+
using namespace std;
  
    const int infty = 1000000000; // uwaga na limit
+
const int infty = 1000000000; // uwaga na limit
    int n,m;
+
int n,m;
    vector< pair<int,int> > adj[100000];
+
vector< pair<int,int> > adj[100000];
  
    vector<int> waga;
+
vector<int> waga;
  
    struct cmp
+
struct cmp
 +
{
 +
    // czy a jest mniejsze od b
 +
    bool operator() (const int &a, const int &b)
 
     {
 
     {
         // czy a jest mniejsze od b
+
         if (waga[a] < waga[b]) return true;
        bool operator() (const int &a, const int &b)
+
        if (waga[a] > waga[b]) return false;
        {
+
        return a<b;
            if (waga[a] < waga[b]) return true;
+
    }
            if (waga[a] > waga[b]) return false;
+
};
            return a<b;
+
        }
+
    };
+
  
  
    set<int, cmp> kopiec; // ;-)
+
set<int, cmp> kopiec; // ;-)
  
  
    void dijkstra(int s)
+
void dijkstra(int s)
 +
{
 +
    int v, u, c;
 +
    waga.clear(); // kasuje wektor
 +
    waga.resize(n, infty); //
 +
   
 +
    waga[s] = 0;
 +
    kopiec.clear();
 +
    kopiec.insert(s);
 +
   
 +
    while( !kopiec.empty() )
 
     {
 
     {
         int v, u, c;
+
         u = *(kopiec.begin());
        waga.clear(); // kasuje wektor
+
         kopiec.erase(kopiec.begin());
         waga.resize(n, infty); //
+
       
     
+
         for (int i=0; i<adj[u].size(); i++)
        waga[s] = 0;
+
        kopiec.clear();
+
         for (int i=0; i<n; i++) kopiec.insert(i);
+
     
+
        while( !kopiec.empty() )
+
 
         {
 
         {
             u = *(kopiec.begin());
+
             v = adj[u][i].first;
             kopiec.erase(kopiec.begin());
+
             c = adj[u][i].second;
         
+
             if (waga[u]+c < waga[v])
             for (int i=0; i<adj[u].size(); i++)
+
 
             {
 
             {
                 v = adj[u][i].first;
+
                 // uaktualniamy wagę wierzchołka v
                c = adj[u][i].second;
+
                kopiec.erase(kopiec.find(v));
                if (waga[u]+c < waga[v])
+
                waga[v] = waga[u]+c;
                {
+
                kopiec.insert(v);
                    // uaktualniamy wagę wierzchołka v
+
                    kopiec.erase(kopiec.find(v));
+
                    waga[v] = waga[u]+c;
+
                    kopiec.insert(v);
+
                }
+
 
             }
 
             }
 
         }
 
         }
     
 
     
 
 
     }
 
     }
 +
   
 +
   
 +
}
  
    int main(void)
+
int main(void)
 +
{
 +
    int a,b,c, s,t;
 +
   
 +
    cin >> n >> m;
 +
    for (int i=0; i<m; i++)
 
     {
 
     {
         int a,b,c, s,t;
+
         cin >> a >> b >> c; // c = koszt krawędzi od a do b
     
+
        adj[a].push_back( pair<int,int>(b,c) );
        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;
+
 
     }
 
     }
</pre>
+
   
[[Użytkownik:Lo|Lo]] 21:51, 23 sty 2007 (CET)
+
    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;
 +
}
 +
</source>
 +
</td>
 +
<td align="center">
 +
<adsense
 +
adclient="pub-2033664350513674"
 +
adslot="5958906648"
 +
adwidth="120"
 +
adheight="600"
 +
/>
 +
</td>
 +
</tr>
 +
</table>
 +
Rafał Nowak 20:24, 1 gru 2007 (CET)

Aktualna wersja na dzień 10:26, 21 sty 2014

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 Plik: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();
    kopiec.insert(s);
 
    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)

Osobiste