Programy

Poniższy program jest przykładową realizacją algorytmu Dijkstry. Definicja danych wejściowych jest następująca:

W pierwszym wierszu program odczytuje numer wierzchołka startowego v0. W następnym wierszu podajemy ilość krawędzi w grafie (skierowanym) m. W m kolejnych wierszach podajemy definicję krawędzi. Definicja składa się z trzech liczb x y w. Pierwsza i druga liczba określa wierzchołki grafu, które są ze sobą połączone tą krawędzią - krawędź biegnie od wierzchołka x do wierzchołka y. Trzecia liczba jest wagą krawędzi.

Na wyjściu program wypisuje znalezione najkrótsze ścieżki od wierzchołka v0 do wszystkich pozostałych wierzchołków. Oprócz ścieżki wypisywany jest również koszt przejścia tej ścieżki.

Do testów można wykorzystać przykładowe dane wejściowe:

1 9 1 2 3 1 4 3 2 3 2 3 1 6 3 6 1 4 5 1 5 3 1 5 6 2 6 4 3

Wersja z wyszukiwaniem liniowym

// I Liceum Ogólnokształcące // im. K. Brodzińskiego // w Tarnowie //-------------------------- // Koło informatyczne 2006/7 //-------------------------- // P012-01 #include <iostream> using namespace std; const int MAX_N = 100; // maksymalna ilość wierzchołków w grafie const int INF = 2147483647; struct TNode { int node; // numer wierzchołka int weight; // waga krawędzi struct TNode * next; // następny element listy }; main() { int i,j,u,n,m,x,y,z,v0; int d[MAX_N+1],p[MAX_N+1]; bool QS[MAX_N+1]; struct TNode *L[MAX_N+1],*pw; // Inicjujemy struktury danych for(i = 1; i <= MAX_N; i++) { d[i] = INF; // koszty dojścia p[i] = 0; // poprzednik na ścieżce QS[i] = false; // przynależność do Q (false) lub S (true) L[i] = NULL; // lista sąsiedztwa } n = 0; // Odczytujemy dane wejściowe cin >> v0; // odczytujemy numer wierzchołka startowego cin >> m; // odczytujemy ilość krawędzi for(i = 1; i <= m; i++) { cin >> x >> y >> z; // odczytujemy krawędź if(x > n) n = x; if(y > n) n = y; pw = new TNode; pw->next = L[x]; pw->node = y; pw->weight = z; L[x] = pw; } cout << endl; d[v0] = 0; // koszt dojścia dla v0 jest zerowy for(i = 1; i <= n; i++) { // szukamy wierzchołka w Q o najmniejszym d u = -1; for(j = 1; j <= n; j++) if(!QS[j] && ((u == -1) || (d[j] < d[u]))) u = j; // znaleziony wierzchołek przenosimy do S QS[u] = true; // Modyfikujemy odpowiednio wszystkich sąsiadów z Q pw = L[u]; while(pw) { if(!QS[pw->node] && (d[pw->node] > d[u] + pw->weight)) { d[pw->node] = d[u] + pw->weight; p[pw->node] = u; } pw = pw->next; } } // Gotowe, wyświetlamy wyniki int stos[MAX_N],ws; for(i = 1; i <= n; i++) { cout << i << ": "; ws = 0; j = i; // Wierzchołki z końca ścieżki umieszczamy na stosie while(j) { stos[ws++] = j; j = p[j]; } // Wypisujemy kolejne wierzchołki ze szczytu stosu while(ws) cout << stos[--ws] << " "; // Wypisujemy koszt dojścia cout << "#" << d[i] << endl; } char s[1]; cin.getline(s,1); cin.getline(s,1); }

1 9 1 2 3 1 4 3 2 3 2 3 1 6 3 6 1 4 5 1 5 3 1 5 6 2 6 4 3 1: 1 #0 2: 1 2 #3 3: 1 2 3 #5 4: 1 4 #3 5: 1 4 5 #4 6: 1 4 5 6 #6

Wersja z kolejką priorytetową opartą na strukturze kopca

// I Liceum Ogólnokształcące // im. K. Brodzińskiego // w Tarnowie //-------------------------- // Koło informatyczne 2006/7 //-------------------------- // P012-02 #include <iostream> using namespace std; const int MAX_N = 100; // maksymalna ilość wierzchołków w grafie const int INF = 2147483647; struct TNode { int node; // numer wierzchołka int weight; // waga krawędzi struct TNode * next; // następny element listy }; main() { int i,j,u,n,m,x,y,z,v0; int d[MAX_N+1],p[MAX_N+1],heap[MAX_N+1],hp[MAX_N+1]; bool QS[MAX_N+1]; struct TNode *L[MAX_N+1],*pw; // Inicjujemy struktury danych for(i = 1; i <= MAX_N; i++) { d[i] = INF; // koszty dojścia p[i] = 0; // poprzednik na ścieżce QS[i] = false; // przynależność do Q (false) lub S (true) L[i] = NULL; // lista sąsiedztwa hp[i] = heap[i] = i; // kopiec } n = 0; // Odczytujemy dane wejściowe cin >> v0; // odczytujemy numer wierzchołka startowego cin >> m; // odczytujemy ilość krawędzi for(i = 1; i <= m; i++) { cin >> x >> y >> z; // odczytujemy krawędź if(x > n) n = x; if(y > n) n = y; pw = new TNode; pw->next = L[x]; pw->node = y; pw->weight = z; L[x] = pw; } cout << endl; int hlen = n; // ilość wierzchołków w kopcu d[v0] = 0; // koszt dojścia dla v0 jest zerowy // Odtwarzamy własność kopca x = heap[1]; heap[1] = heap[v0]; heap[v0] = x; hp[v0] = 1; hp[1] = v0; for(i = 1; i <= n; i++) { u = heap[1]; // Usuwamy korzeń i odtwarzamy własność kopca int parent; heap[1] = heap[hlen]; hlen--; hp[heap[1]] = parent = 1; while(true) { int left = parent + parent; int right = left + 1; if(left > hlen) break; int dmin = d[heap[left]]; int pmin = left; if((right <= hlen) && (dmin > d[heap[right]])) { dmin = d[heap[right]]; pmin = right; } if(d[heap[parent]] <= dmin) break; x = heap[parent]; heap[parent] = heap[pmin]; heap[pmin] = x; hp[heap[parent]] = parent; hp[heap[pmin]] = pmin; parent = pmin; } // znaleziony wierzchołek przenosimy do S QS[u] = true; // Modyfikujemy odpowiednio wszystkich sąsiadów z Q pw = L[u]; while(pw) { if(!QS[pw->node] && (d[pw->node] > d[u] + pw->weight)) { d[pw->node] = d[u] + pw->weight; p[pw->node] = u; // Po zmianie d[v] odtwarzamy własność kopca int child = hp[pw->node]; while(child > 1) { parent = child / 2; if(d[heap[parent]] <= d[heap[child]]) break; x = heap[parent]; heap[parent] = heap[child]; heap[child] = x; hp[heap[parent]] = parent; hp[heap[child]] = child; child = parent; } } pw = pw->next; } } // Gotowe, wyświetlamy wyniki int stos[MAX_N],ws; for(i = 1; i <= n; i++) { cout << i << ": "; ws = 0; j = i; // Wierzchołki z końca ścieżki umieszczamy na stosie while(j) { stos[ws++] = j; j = p[j]; } // Wypisujemy kolejne wierzchołki ze szczytu stosu while(ws) cout << stos[--ws] << " "; // Wypisujemy koszt dojścia cout << "#" << d[i] << endl; } char s[1]; cin.getline(s,1); cin.getline(s,1); }

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe