Najkrótsze ścieżki 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 albo zaadaptować drzewo przedziałowe (wystarczy zaimplementować operacje wykorzystywane przez algorytm Dijkstry) 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 samodzielnie zaimplementować kopiec binarny albo zaadaptować drzewo przedziałowe (wystarczy zaimplementować operacje wykorzystywane przez algorytm Dijkstry).

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?