Michał Małek Warszawa, 2010-06-02

Wyznaczanie najkrótszej ścieżki

pomiędzy dwoma węzłami grafu (Prolog + Java)

1. Ogólny opis problemu

Zadanie polega na napisaniu programu umożliwiającego stworzenie oraz edycję grafu oraz po wybraniu dwóch jego węzłów obliczenie najkrótszej ścieżki pomiędzy nimi.

1. Interfejs graficzny

Interfejs graficzny powinien umożliwiać graficzną edycję grafu (zmiana rozmieszczenia węzłów grafu, tworzenie nowego węzła, usuwanie istniejących węzłów, tworzenie/usuwanie krawędzi).

Po wybraniu 2 węzłów uaktywni się menu wybierania najkrótszej ścieżki pomiędzy wybranymi węzłami. Wynik takiej operacji przedstawiony zostanie na aktualnie wyświetlanym grafie (pogrubione/pokolorowane krawędzie, kolor wierzchołka początkowego i końcowego zmieni się na inny). W przypadku wszelkiego typu błędów wyświetlone zostanie okno z opisem błędu i ewentualnym sposobem jego naprawy.

1. Moduł obliczeniowy

Po uruchomieniu procedury wyznaczania najkrótszej ścieżki pomiędzy dwoma węzłami uaktywni się moduł obliczeniowy.

Na początku zostanie wybrany algorytm wyznaczający ścieżkę (język Java). Po wybraniu odpowiedniego algorytmu graf zostanie wyeksportowany do pliku Prologa. Następnie zostanie uruchomiony odpowiedni algorytm.

Wykonanie algorytmu odbędzie się w środowisku Prolog. Wyniki działania zostaną przetworzone przez moduł obliczeniowy, a następnie wyświetlone (przez uaktualnienie grafu/wyświetlenie okna błędów) użytkownikowi.

Wybrane algorytmy do implementacji (język Prolog) :

- algorytm Dijkstry (dla grafu ważonego)

- algorytm Bellmana – Forda (dla grafu ważonego z ujemnymi wagami)

- algorytm przeszukiwania wszerz BFS (dla grafu nie ważonego).

Uwaga : Podane algorytmy mogą ulec zmianie.