Wyobraź sobie, że masz sieć połączeń pomiędzy miastami; każde połączenie ma przypisany pewien koszt, oraz że chcesz znaleźć najtańszą drogę od miasta A do miasta B. Jak taki problem rozwiązać? Jak robią to: Google Maps, albo każdy dobry Nawigator GPS?
Rzecz jasna --- korzystają z algorytmu Dijkstry. Wczoraj na naszych lekcjach opowiedzieliśmy sobie, jak on działa. W załączniku znajduje się moja prezentacja zawierająca symulację działania tego algorytmu i nie tylko (o tym porozmawiamy po feriach).
W skrócie, algorytm Dijkstry służy do znajdowania najkrótszych ścieżek z wybranego wierzchołka (źródła) do wszystkich pozostałych wierzchołków w grafie ważonym z nieujemnymi wagami. Oto jego zapis w pseudojęzyku
 Założenie, że w grafie wszystkie wagi na krawędziach są nieujemne jest bardzo istotne. Spróbuj skonstruować przykład grafu, dla którego algorytm Dijkstry źle zadziała, tj. nie znajdzie najkrótszych ścieżek od źródła. Wskazówka: twój graf powinien mieć co najmniej jedną krawędź z ujemną wagą :-) ImplementacjaUwaga poniższy kod został napisany na sucho, tzn. nawet go nie kompilowałem. Zresztą na pewno by się skompilował, bo wczytywanie grafu poniżej zostało podane jako przykład. Nie umieściłem go nawet w żadnej funkcji. W poniższym programie brakuje nawet funkcji main. Poniższy program proszę potraktować jako materiał dydaktyczny, a nie kod gotowy do zastosowania techniki Kopiego Pejsta (CTRL+C, CTRL+V). W poniższym programie zastosowałem inny sposób realizacji kolejki priorytetowej niż zrobiłem to kiedyś na mojej RNO-Wiki, czyli tutaj. #include<queue> #include<vector> #include<iostream> using namespace std; vector< pair<int,int> > G[1000000]; // reprezentacja grafu z wagami //~~~~~~~~~~~~~~~~~~~~~~~ /** Wczytywanie grafu **/ //~~~~~~~~~~~~~~~~~~~~~~~ int n,m; cin >> n >> m; // wczytaj liczbę wierzchołków i krawędzi for (int i=0; i<m; i++) { cin >> a >> b >> c; // wczytaj krawędź a--b z kosztem c G[a].push_back( make_pair(b,c) ); G[b].push_back( make_pair(a,c) ); // assert( c>=0 ); // upewnij się, że wagi są nieujemne } //~~~~~~~~~~~~~~~~~~~~~~~ /** Algorytm Dijkstry **/ //~~~~~~~~~~~~~~~~~~~~~~~~ int dist[1000000]; // tablica obliczonych odległości od źródła bool mark[1000000]; // będziemy zaznaczali wierzchołki, które zostały z kolejki usunięte #define INF 2000000000 priority_queue< pair<int,int> > Q; // kolejka wierzchołków do obsługiwania // zasada jest taka: w kolejce trzymamy pary (-c, u), gdzie c oznacza koszt // ścieżki do źródła z wierzchołka o numerze u void dijkstra(int s) // s = source, czyli numer wierzchołka (źródła) { int u,d; // inicjalizacja for (int u=0; u<n; u++) { mark[u] = false; dist[u] = INF; } dist[s] = 0; // ustawiamy odległość źródła od źródła na zero Q.push( make_pair(0,s) ); // wstawiamy wierzchołek s do kolejki while( !Q.empty() ) { // wyciągamy wierzchołek nr u, dla którego odległość d od źródła s jest najmniejsza u = Q.front().second(); d = -Q.front().first(); Q.pop(); if ( mark[u]==true ) continue; // jeśli już go kiedyś usunęliśmy, to możemy nic nie robić, bo na pewno wtedy miał mniejsze d mark[u] = true; // oznaczamy, że wierzchołek u został usunięty z kolejki for (int i=0; i<G[u].size(); i++) { // rozpatrujemy krawędź u--v z kosztem c int v = G[u][i].first(); int c = G[u][i].second(); // jeśli v nie ma jeszcze obliczonej najkrótszej odległości od źródła s, // oraz to co ma dotychczas obliczone da się poprawić, to poprawiamy if ( !mark[v] && dist[v] > dist[u]+c ) { dist[v] = dist[u]+c; Q.push( make_pair(-dist[v],v) ); // i wstawiamy v do kolejki // Uwaga: może się więc zdażyć, że v jest kilka razy w kolejce // nie przeszkadza nam to, bo razem z v są różne koszty. // Gdy będziemy usuwali v z kolejki, to na pewno weźmiemy tego z najmniejszą odległością od źródła // Następnych będziemy po prostu pomijali, czyli usuwali nic nie robiąc (patrz na instrukcję continue sprzed 18 wierszy) } } } }Prezentacja działania |
|
|
