Najkrótsze ścieżki w grafie (projekt)

Spis Treści

Wymagania i kryteria oceniania

Należy zaimplementować jeden z niżej wymienionych algorytmów wyszukujących najkrótsze ścieżki w grafie i opanować (ze zrozumieniem) dotyczącą go teorię. Ocena zależy od wybranego wariantu i może być podwyższona o 0,5 stopnia za oddanie programu w pierwszym terminie, z bezbłędną odpowiedzią.

Warianty

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

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.

Na ocenę 3 można użyć implementacji kolejki z bibliotek języka, np. deque w Pythonie albo C++. Na ocenę 3,5 należy samodzielnie zaimplementować kolejkę (np. za pomocą listy jednokierunkowej) z operacjami dodawania i usuwania o stałej złożoności czasowej.

Graf z wagami - algorytm Dijkstry (na ocenę 3,5 albo 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.

Na ocenę 3,5, w roli kolejki priorytetowej można wykorzystać zwykłą tablicę (indeksowaną numerami wierzchołków) lub implementację kopca binarnego z bibliotek języka, np. heapq w Pythonie albo priority_queue w C++. Na ocenę 4 należy samodzielnie zaimplementować kopiec binarny albo zaadaptować drzewo przedziałowe (wystarczy zaimplementować operacje wykorzystywane przez algorytm Dijkstry).

Graf z wagami i zadanymi momentami opuszczenia wierzchołków - zmodyfikowany algorytm Dijkstry (na ocenę 4,5 albo 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).

Na ocenę 4,5, w roli kolejki priorytetowej można wykorzystać zwykłą tablicę (indeksowaną numerami wierzchołków) lub implementację kopca binarnego z bibliotek języka, np. heapq w Pythonie albo priority_queue w C++. Na 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ę 3,5-4, a potem dokonać odpowiedniej modyfikacji.

Przykładowe pytania sprawdzające