Algorytm Prima-Dijkstry
Z RNO-Wiki
(Różnice między wersjami)
(Nowa strona: Algorytm Prima-Dijkstry służy do znajdowania minimalnego drzewa spinającego pewnego grafu z wagami na krawędziach. W problemie chodzi o wybranie takich krawędzi, aby powstały pod...) |
m (Wycofano edycję użytkownika Quentinscott (dyskusja). Autor przywróconej wersji to Adminek.) |
||
(Nie pokazano 5 wersji utworzonych przez 4 użytkowników) | |||
Linia 1: | Linia 1: | ||
− | Algorytm Prima-Dijkstry służy do znajdowania minimalnego drzewa spinającego pewnego grafu z wagami na krawędziach. | + | [[Kategoria:Algorytmy grafowe]] |
+ | Algorytm Prima-Dijkstry służy do znajdowania minimalnego drzewa spinającego pewnego grafu z wagami na krawędziach. Przeczytaj także artykuł o [[Algorytm Kruskala|algorytmie Kruskala]]. | ||
W problemie chodzi o wybranie takich krawędzi, aby powstały podgraf spinał wszystkie wierzchołki (tj. aby był spójny) i aby suma wag wybranych krawędzi była minimalna. | W problemie chodzi o wybranie takich krawędzi, aby powstały podgraf spinał wszystkie wierzchołki (tj. aby był spójny) i aby suma wag wybranych krawędzi była minimalna. | ||
Poniżej znajduje się implementacja algorytmu Prima-Dijkstry w języku C++. Nie bez powody pojawia się tu nazwisko Dijkstry. Zobacz [[Algorytm Dijkstry]], a stwierdzisz, że to prawie to samo. Ciekawe, co Prim tutaj dodał :-) | Poniżej znajduje się implementacja algorytmu Prima-Dijkstry w języku C++. Nie bez powody pojawia się tu nazwisko Dijkstry. Zobacz [[Algorytm Dijkstry]], a stwierdzisz, że to prawie to samo. Ciekawe, co Prim tutaj dodał :-) | ||
+ | |||
+ | <table width="100%"> | ||
+ | <tr> | ||
+ | <td valign="top"> | ||
<source lang="cpp"> | <source lang="cpp"> | ||
Linia 118: | Linia 123: | ||
printf("Drzewo złożone jest z następujących krawędzi:\n"); | printf("Drzewo złożone jest z następujących krawędzi:\n"); | ||
for (int i=1; i<n; i++) // specjalnie pomijam wierzhołek nr 0 | for (int i=1; i<n; i++) // specjalnie pomijam wierzhołek nr 0 | ||
− | printf("%d -- %d\n", i+1, pi[i]+1); | + | // zwiekszam numery, bo zakładam, że na wejściu wierzchołki numerowane są od 1 |
+ | printf("%d -- %d\n", i+1, pi[i]+1); | ||
return 0; | return 0; | ||
} | } | ||
</source> | </source> | ||
+ | </td> | ||
+ | <td width="140" align="center"> | ||
+ | <adsense | ||
+ | adclient="pub-2033664350513674" | ||
+ | adslot="5958906648" | ||
+ | adwidth="120" | ||
+ | adheight="600" | ||
+ | /> | ||
+ | </td> | ||
+ | </tr> | ||
+ | </table> |
Aktualna wersja na dzień 21:06, 21 cze 2011
Algorytm Prima-Dijkstry służy do znajdowania minimalnego drzewa spinającego pewnego grafu z wagami na krawędziach. Przeczytaj także artykuł o algorytmie Kruskala.
W problemie chodzi o wybranie takich krawędzi, aby powstały podgraf spinał wszystkie wierzchołki (tj. aby był spójny) i aby suma wag wybranych krawędzi była minimalna.
Poniżej znajduje się implementacja algorytmu Prima-Dijkstry w języku C++. Nie bez powody pojawia się tu nazwisko Dijkstry. Zobacz Algorytm Dijkstry, a stwierdzisz, że to prawie to samo. Ciekawe, co Prim tutaj dodał :-)
/** * Autor: Rafał Nowak * Data : 2008.02.27 * * W pracy tej zaimplementowana algorytm Prima-Dijkstry znajdowania minimalnego * drzewa spinajacego (MST). * * Dany: nieskierowany graf G z wagami na krawędziach * Przykładowe wejście: 6 10 1 2 2 1 6 1 1 5 3 4 1 5 2 6 2 2 3 5 4 3 4 3 5 4 4 5 4 5 6 3 **/ #include<cstdio> #include<vector> #include<set> using namespace std; const int infty = 1000000000; // uwaga na limit int n,m; vector< vector< pair<int,int> > > adj; vector<bool> vis; vector<int> waga, pi; 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 prim_dijkstra(int s) { int v, u, c; waga.clear(); waga.resize(n, infty); vis.clear(); vis.resize(n,false); pi.resize(n); waga[s] = 0; pi[s]=s; kopiec.clear(); for (int i=0; i<n; i++) kopiec.insert(i); // MST to drzewo zawierające wierzchołki, których nie w zbiorze kopiec, // czyli na razie jest ono pustym drzewem. while( !kopiec.empty() ) { u = *(kopiec.begin()); // weź wierzchołek najbliżej drzewa MST kopiec.erase(kopiec.begin()); vis[u]=true; // dodajemy wierzchołek v do drzewa MST // a dodał go wierzchołek pi[u] for (int i=0; i<adj[u].size(); i++) { v = adj[u][i].first; if (!vis[v]) { c = adj[u][i].second; if (c < waga[v]) // w alg. Dijkstry jest tutaj waga[u]+c < waga[v] { // uaktualniamy wagę wierzchołka v kopiec.erase(kopiec.find(v)); waga[v] = c; // w alg. Dijkstry jest tutaj waga[v]=waga[u]+c; kopiec.insert(v); pi[v] = u; } } } } } int main(void) { int a,b,c; scanf("%d %d", &n, &m); adj.resize(n); for (int i=0; i<m; i++) { scanf("%d %d %d", &a, &b, &c); // c = koszt krawędzi od a do b a--; b--; adj[a].push_back( make_pair(b,c) ); adj[b].push_back( make_pair(a,c) ); } prim_dijkstra(0); // zaczynamy algorytm w wierzchołku nr 0 // alg. Dijkstry wypełni całą tablicę pi[..] krawędziami drzewa MST // suma wag waga[..], daje wagę całego drzewa MST int suma = 0; for (int i=1; i<n; i++) suma += waga[i]; // uwaga, bo waga[0]=0 printf("Koszt minimalnego drzewa spinającego wynosi %d\n", suma); printf("Drzewo złożone jest z następujących krawędzi:\n"); for (int i=1; i<n; i++) // specjalnie pomijam wierzhołek nr 0 // zwiekszam numery, bo zakładam, że na wejściu wierzchołki numerowane są od 1 printf("%d -- %d\n", i+1, pi[i]+1); return 0; } |
|