Dydaktyka‎ > ‎Notatki‎ > ‎

Algorytm Dijkstry

opublikowane: 10 lut 2011, 00:19 przez Rafał Nowak   [ zaktualizowane 3 mar 2016, 00:36 przez Rafał Nowak ]
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ą :-)

Implementacja

Uwaga 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
Algorytmy grafowe
Ċ
Rafał Nowak,
10 lut 2011, 00:46
Comments