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. def IleZamianPowrot(macierz, start, koniec):
2.   n = len(macierz)
3.   tab = []
4.   for i in range(0, len(macierz)):
5.     tab.append(dane(sys.maxsize, 0, -1))
6.   tab[start].odległość = 0
7.   tab[start].zamian = 0
8.   tab[koniec].zamian = -1
9.   q = queue.Queue()
10.   q.put(start)
11.   while not q.empty():
12.     u = q.get()
13.     odleglosc_nowa = tab[u].odległość
14.     for i in range(n):
15.       if (macierz[u][i] == 0 and macierz[i][u] == 0):
16.         continue
17.       zamian_nowa = tab[u].zamian
18.       if (macierz[u][i] == 0 and macierz[i][u] == 1):
19.         zamian_nowa += 1
20.       if (tab[i].odległość == sys.maxsize
21.         or zamian_nowa < tab[i].zamian
22.         or (zamian_nowa == tab[i].zamian
23.           and odleglosc_nowa < tab[i].odległość)):
24.         tab[i].odległość = tab[u].odległość + 1
25.         tab[i].zamian = zamian_nowa
26.         tab[i].poprzednik = u
27.         q.put(i)
28.   return tab[koniec]

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. n = int(input("Podaj ile węzłów ma graf\n n = "))
2. s = int(input("Podaj węzeł startowy\n s = "))
3. k = int(input("Podaj węzeł końcowy\n k = "))
4. print("Podaj elementy macierzy:")
5. macierz = []
6. for i in range(0, n):
7.   tab = [int(x) for x in input().split()]
8.   macierz.append(tab)
9.  
10. wynik = IleZamianPowrot(macierz, s, k)
11. print("Potrzebnych zamian", wynik.zamian, end=", ")
12. print("odległość", wynik.odległość)

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