Najkrótsze ścieżeki w grafie (algorytmy w Pythonie; projekt)

Warianty zadania na różne oceny z algorytmów

Graf bez wag - przeszukiwanie grafu wszerz (na ocenę 3)

Należy zaimplementować algorytm przeszukiwania grafu wszerz, znajdujący najbliższą ścieżkę w grafie skierowanym bez wag, dla zadanej pary wierzchołków: początkowego i końcowego.

Algorytm powinien znaleźć zarówno długość najkrótszej ścieżki (liczbę krawędzi do przebycia), jak i samą ścieżkę (ciąg wierzchołków przez które ta ścieżka przebiega). Algorytm powinien też zwracać odpowiednią informację, jeśli nie istnieje żadna ścieżka od zadanego wierzchołka początkowego do końcowego.

W roli kolejki można użyć standardowego typu deque. Alternatywnie, można samemu zaimplementować kolejkę (np. za pomocą listy jednokierunkowej) i otrzymać o 0,5 wyższą ocenę (tj. 3,5), ale pod warunkiem, że wykorzystywane operacje dodawania i usuwania z kolejki będą działały w czasie stałym.

Graf z wagami - algorytm Dijkstry (na ocenę 4)

Należy zaimplementować algorytm Dijkstry, znajdujący najbliższą ścieżkę w grafie skierowanym z wagami, dla zadanej pary wierzchołków: początkowego i końcowego.

Algorytm powinien znaleźć zarówno długość najkrótszej ścieżki (sumę wag jej krawędzi), jak i samą ścieżkę (ciąg wierzchołków przez które ta ścieżka przebiega). Algorytm powinien też zwracać odpowiednią informację, jeśli nie istnieje żadna ścieżka od zadanego wierzchołka początkowego do końcowego.

W roli kolejki priorytetowej można wykorzystać zwykłą tablicę (indeksowaną numerami wierzchołków) lub standardową implementację kopca binarnego heapq. Alternatywnie, można samemu zaimplementować kopiec binarny i otrzymać o 0,5 wyższą ocenę (tj. 4,5).

Graf z wagami i zadanymi momentami opuszczenia wierzchołków - zmodyfikowany algorytm Dijkstry (na ocenę 5)

Ten wariant zadania opiszemy przez analogię do podróżowania autobusami (lub pociągami) pomiędzy miastami (utożsamianymi z wierzchołkami grafu). Dla każdego przejazdu (krawędzi), zadany jest nie tylko czas jego trwania (waga; podany w minutach), ale także możliwe momenty możliwych odjazdów (podane w minutach które upłynęły od początku całej podróży). Czasami trzeba więc zaczekać na możliwość przejazdu.

Dla przykładu, załóżmy że w 23. minucie podróży znaleźliśmy się w mieście (wierzchołku) A, i że chcemy się przemieścić do miasta B. Znany jest czas przejazdu z A do B wynoszący 20 minut i możliwe momenty wyruszenia z A do B: 8., 28., i 55. minuta. W wierzchołku B możemy znaleźć się po 25 minutach, na które składa się czas czekania na odjazd (28m-23m=5m) i czas przejazdu (20m). Czyli w B możemy się się znaleźć w 23+25=28+20=48 minucie całej podróży.

Należy zaimplementować odpowiednio zmodyfikowany algorytm Dijkstry, który powinien obliczyć plan najkrótszej możliwej podróży od zadanego miasta początkowego do zadanego miasta końcowego, tj. ciąg kolejno odwiedzanych miast wraz z momentami przybycia do nich. Ponieważ zakładamy że podróż rozpoczyna się w momencie czasowym 0, to całkowity czas podróży pokrywa się z momentem przybycia do miasta końcowego. Algorytm powinien też zwracać odpowiednią informację, jeśli nie istnieje możliwość przejazdu z miasta początkowego do końcowego (czasami brak takiej możliwości będzie wynikał z niemożności zdążenia na ostatni autobus lub pociąg).

W roli kolejki priorytetowej można wykorzystać zwykłą tablicę (indeksowaną numerami wierzchołków) lub standardową implementację kopca binarnego heapq, ale wtedy ocena zostanie obniżona do o 0,5 stopnia (tj. do 4,5). By uzyskać pełną ocenę (5), należy samemu zaimplementować kopiec binarny.

Wskazówka: można zacząć pracę od zaimplementowania wariantu na ocenę 4, a potem dokonać odpowiedniej modyfikacji.

Wymagania dotyczące programowania (wariant podstawowy, na ocenę 3)

Kod programu powinien być możliwie przejrzysty i czytelny.

Graf wejściowy można zaszyć na stałe w kodzie programu.

Rozszerzenia, na wyższe oceny z programowania

Wczytywanie grafu z pliku (+1 do oceny)

Graf wejściowy należy wczytać z pliku tekstowego.

Proponowany format pliku:

• Pierwsza linia zawiera cztery liczby naturalne, v, e, s, k, oddzielone spacjami i oznaczające kolejno:

  • v - liczbę wierzchołków w grafie,
  • e - liczbę krawędzie w grafie,
  • s - numer wierzchołka początkowego,
  • k - numer wierzchołka końcowego.

  Zakładamy, że wierzchołki są ponumerowane liczbami naturalnymi od 0 do v-1, więc s oraz k są liczbami z takiego właśnie zakresu.

• Kolejne e linii zawiera opisy krawędzi, każdy z nich składa się z ciągu liczb naturalnych, oddzielonych spacjami. Kolejne liczby oznaczają:

  1. numer wierzchołka z którego krawędź wychodzi,
  2. numer wierzchołka do którego krawędź wchodzi,
  3. (tylko w przypadku wariantów na ocenę 4 i 5 z algorytmów) waga krawędzi (w wariancie na 5 z algorytmów interpretowana jako czas przejazdu przez krawędź w minutach),
  4. (tylko w przypadku wariantu na ocenę 5 z algorytmów) możliwe momenty odjazdu, podane w minutach które upłynęły od początku całej podróży (jedna lub więcej liczb w kolejności rosnącej).

Narysowanie grafu z zaznaczoną najkrótszą ścieżką (+1 do oceny)

Program powinien narysować graf (np. wyświetlić na ekranie lub zapisać do pliku graficznego), zaznaczając na nim przebieg najkrótszej ścieżki.

W leżących na najkrótszej ścieżce wierzchołkach należy wpisać:

• (w przypadku wariantu na 3 z algorytmów) numery zgodne z kolejnością odwiedzania wierzchołków (0 dla wierzchołka początkowego i liczoną krawędziami długość trasy dla końcowego),
• (w przypadku wariantu na 4 z algorytmów) sumaryczną wagę pokonanych krawędzi (0 dla wierzchołka początkowego i długość trasy dla końcowego),
• (w przypadku wariantu na 5 z algorytmów) moment czasowy przybycia do wierzchołka (0 dla wierzchołka początkowego i całkowity czas przejazdu dla końcowego).

Do rysowania wolno użyć bibliotek zewnętrznych, np. graphviz lub pydot (uwaga: do poprawnego działania, te biblioteki wymagają zainstalowanego pakietu graphviz i programu dot w ścieżkach systemowych).

Przykładowe pytania sprawdzające z algorytmów

• Zilustrować działanie zaimplementowanego algorytmu dla zadanego grafu.
• Jaka jest złożoność czasowa oraz pamięciowa zaimplementowanego algorytmu?
• Jak działa użyta kolejka? Jaka jest złożoność jej operacji?

Przykładowe pytania sprawdzające z programowania

• Wyjaśnić jak działa użyta w programie składnia Pythona albo funkcja.
• Za co odpowiedzialna jest w programie wskazana linia?