Podróż z Powrotem

Zadanie

Dany jest graf skierowany o n wierzchołkach. Napisz algorytm, który znajdzie najmniejszą liczbę krawędzi, które trzeba zamienić, aby można było dojść od punktu początkowego do końcowego.

Przykład

Dany jest przykładowo następujący graf skierowany o 5 wierzchołkach. Szukamy drogi od A do E tak, aby trzeba było odwrócić jak najmniej krawędzi.

Przykładowy graf

Najkrótsz ścieżka ma długość 2 i prowadzi A-D-E. Pokonanie takiej drogi wymaga odwrócenia dwóch krawędzi. Jednak jeśli wybierzemy trasę A-B-C-E to odwrócona zostanie tylko jedna krawędź. To jest ścieżka, którą należy wybrać, ponieważ chcemy ścieżkę na której trzeba dokonać jak najmniej odwróceń (idealnie jeśli nie trzeba wogle).

Analiza zadania

Zadanie można rozwiązać przy pomocy algorytmu BFS. Rozpoczynamy poszukiwania od węzła początkowego, a następnie dołączamy jego sąsiadów pod warunkiem, że ścieżka prowadząca do nich jeszcze nie istnieje lub liczba zamian nowej ścieżki jest mniejsza niż dotychczas znaleziona. W przypadku, gdy liczba zamian jest taka sama to należy wybrać krótszą ścieżkę.

Przykładowa dla podanego wyżej grafu rozpoczynamy poszukiwania od wierzchołka A. Dla każdego wierzchołka została podana jego aktualna odległość oraz ile trzeba było dokonać zamian.

Algorytm skończył działanie, ponieważ kolejka jest pusta. Zwracana jest para wartości zgromadzona dla wierzchołka E. W tym przypadku odległość wynosi 3 i potrzeba zrobić dokładnie jedną zamianę.

Implementacja

Poniższa funkcja IleZamianPowrot() zwraca informację dla podanej macierzy długość ścieżki od start do koniec oraz informację ile krawędzi trzeba odwrócić.

1. dane IleZamianPowrot(int** macierz, int n, int start, int koniec) {
2.   dane* tab = new dane[n];
3.   for (int i = 0; i < n; i++) {
4.     tab[i].odleglosc = INT32_MAX;
5.     tab[i].zamian = 0;
6.   }
7.   tab[start].odleglosc = 0;
8.   tab[start].zamian = 0;
9.   tab[koniec].zamian = -1;
10.   queue<int> q;
11.   q.push(start);
12.   while (q.size() != 0) {
13.     int u = q.front();
14.     q.pop();
15.     int odleglosc_nowa = tab[u].odleglosc;
16.     for (int i = 0; i < n; i++) {
17.       if (macierz[u][i] == 0 && macierz[i][u] == 0) {
18.         continue;
19.       }
20.       int zamian_nowa = tab[u].zamian;
21.       if (macierz[u][i] == 0 && macierz[i][u] == 1) {
22.         zamian_nowa++;
23.       }
24.       if (tab[i].odleglosc == INT32_MAX
25.         || zamian_nowa < tab[i].zamian
26.         || (zamian_nowa == tab[i].zamian
27.           && odleglosc_nowa < tab[i].odleglosc)) {
28.         tab[i].odleglosc = tab[u].odleglosc + 1;
29.         tab[i].zamian = zamian_nowa;
30.         tab[i].poprzednik = u;
31.         q.push(i);
32.       }
33.     }
34.   }
35.   return tab[koniec];
36. }

Na początku algorytm inicjalizuje pustą tablicę dla każdego wierzchołka. Wierzchołkowi początkowemu i końcowemu nadawane są wartości początkowe. Następnie na kolejkę wrzucany jest wierzchołek początkowy i rozpoczyna się przeszukiwanie grafu i jego odpowiednia aktualizacja.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższej funkcji, która wczyta potrzebne dane:

1. int main() {
2.   int n, start, koniec;
3.   cout << "Podaj ile jest wierzcholkow w grafie\n n = ";
4.   cin >> n;
5.   cout << "Podaj wezel poczatkowy\n s = ";
6.   cin >> start;
7.   cout << "Podaj wezel koncowy\n k = ";
8.   cin >> koniec;
9.   cout << "Podaj macierz grafu:\n";
10.   int** macierz = new int*[n];
11.   for (int i = 0; i < n; i++) {
12.     macierz[i] = new int[n];
13.     for (int j = 0; j < n; j++) {
14.       cin >> macierz[i][j];
15.     }
16.   }
17.   dane wynik = IleZamianPowrot(macierz, n, start, koniec);
18.   cout << "Potrzebnych zamian " << wynik.zamian;
19.   cout << ", odleglosc " << wynik.odleglosc;
20.   system("pause");
21.   return 0;
22. }

Przykładowy graf

Podany graf należy wpisać jako następującą macierz:

1. 0 1 0 0 0
2. 0 0 0 0 0
3. 0 1 0 0 1
4. 1 0 0 0 0
5. 0 0 0 1 0

• Kod źródłowy Implementacja