Algorytm Dijkstry

Z RNO-Wiki
(Różnice między wersjami)
m (Implementacja w C++)
m (Implementacja w C++)
Linia 1: Linia 1:
 
== 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''']]:
 +
<table width="100%">
 +
<tr>
 +
<td valign="top">
 
<source lang="cpp">
 
<source lang="cpp">
 
#include<iostream>
 
#include<iostream>
Linia 79: Linia 82:
 
}
 
}
 
</source>
 
</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)
 
Rafał Nowak 20:24, 1 gru 2007 (CET)

Wersja z 19:29, 1 gru 2007

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)

Osobiste