Badanie efektywności algorytmów grafowych w zależności od rozmiaru instancji oraz sposobu reprezentacji grafu w pamięci komputera.
Autor: Artur Kręgiel
Prowadzący: dr inż. Zbigniew Buchalski
Pełny opis projektu znajduje się na tej stronie.
Należało zaimplementować oraz dokonać pomiaru czasu działania wybranych algorytmów grafowych rozwiązujących następujące problemy:
- wyznaczanie minimalnego drzewa rozpinającego (MST) - algorytm Prima oraz algorytm Kruskala,
- wyznaczanie najkrótszej ścieżki w grafie – algorytm Dijkstry oraz algorytm Forda-Bellmana,
Algorytmy te należy zaimplementować dla obu poniższych reprezentacji grafu w pamięci komputera:
- reprezentacja macierzowa (macierz incydencji),
- reprezentacja listowa (lista następników/poprzedników).
Projekt, za zgodą prowadzącego, został zaimplementowany w języku programowania Go.
$ go build -o aizo2
$ ./aizo2
Program można również uruchomić bez wyraźnego budowania projektu:
$ go run .