Algorytm Floyda-Warshalla (projekt)

Spis Treści

Obliczanie odległości (wariant podstawowy, na ocenę 3)

Należy zaimplementować algorytm Floyda-Warshalla w wersji obliczającej odległości pomiędzy każdą parą wierzchołków w grafie ważonym.

Dodatkowo należy opanować (ze zrozumieniem) teorię dotyczącą tego algorytmu: zasadę działania, złożoność obliczeniową czasową i pamięciową, a także zrozumieć ideę programowania dynamicznego.

Ocena może być podwyższona o 0,5 stopnia za oddanie programu w pierwszym terminie, z bezbłędną odpowiedzią.

Odnalezienie ścieżek (rozszerzenie na ocenę 4)

Algorytm oprócz odległości powinien znaleźć także same ścieżki (konkretnie dwuwymiarową tablice pozwalającą na ich szybkie wyznaczanie). Sam program powinien wypisywać ścieżki pomiędzy wskazanymi wierzchołkami.

Zarówno początek, jak i koniec ścieżki, mogą leżeć na krawędzi (rozszerzenie na ocenę 5)

Za pomocą algorytmu Floyda-Warshalla należy wyznaczyć obie, dwuwymiarowe tablice: tą z odległościami, oraz tą pozwalającą odtwarzać ścieżki. Można założyć, że graf jest nieskierowany.

Następnie należy wyznaczyć najkrótszą ścieżkę, od zadanego punktu P, do zadanego punktu K, przy założeniu, że zarówno P, jak i K, mogą leżeć zarówno w wierzchołku grafu, jak i na jego krawędzi. Przy czym położenie punktu na krawędzi A-B o wadze W, określamy za pomocą liczby L (można się ograniczyć do liczb całkowitych) z przedziału od 0 do W, gdzie: 0 oznacza, że punkt leży w wierzchołku A; W/2, że leży dokładnie po środku krawędzi; zaś W, że leży w wierzchołku B. Ogólnie, odległość od tego punktu do A wynosi L, zaś do B wynosi W-L.

Jeżeli oba punkty, P i K, leżą na tej samej krawędzi, to zakładamy, że najkrótsza ścieżka pomiędzy nimi przebiega wyłącznie po fragmencie tej krawędzi.

Jeżeli punkty P i K leżą na różnych krawędziach, to możemy szybko wyznaczyć ścieżkę pomiędzy nimi, korzystając ze spostrzeżenia, że ma ona następujący przebieg:

  1. wpierw z P idzie do jednego z (dwóch) wierzchołków krawędzi, na której leży P (należy sprawdzić obie możliwości i wybrać tę, która finalnie da krótszą ścieżkę);
  2. potem z tego wierzchołka idzie to jednego z (dwóch) wierzchołków krawędzi, na której leży K (tę część ścieżki można szybko obliczyć używając macierzy wyznaczonych zawczasu za pomocą algorytmu Floyda-Warshalla; znów należy sprawdzić obie możliwości);
  3. końcowy fragment ścieżki przebiega po krawędzi, na której leży K.

By pokazać przykładowe zastosowanie dla opisanego algorytmu, wyobraźmy sobie, że piszemy grę typu PacMan i chcemy wyznaczyć najkrótszą ścieżkę od jednego z duszków do PacMana. Przy tym zależy nam, by zrobić to szybko, ze względu na dużą częstość, z jaką musimy rozwiązać ten problem. Szczęśliwie kształt samego labiryntu się nie zmienia, przynajmniej dopóki nie ukończymy poziomu. Dlatego można za pomocą algorytmu Floyda-Warshalla jednorazowo policzyć ścieżki pomiędzy wszystkimi parami skrzyżowań na planszy, a następnie korzystać z wyników tych obliczeń, by wielokrotnie rozwiązywać postawiony problem. Przy czym przez skrzyżowania rozumiemy takie punkty, z których można się przemieścić w co najmniej trzech kierunkach. Te punkty są wierzchołkami grafu podawanego na wejściu algorytmu Floyda-Warshalla. Parę wierzchołków w tym grafie łączy krawędź wtedy i tylko wtedy gdy łączy je w labiryncie droga nieprzechodząca przez inne skrzyżowania. Długość tej drogi wyznacza wagę krawędzi.

By zaliczyć projekt na 5 nie trzeba jednak ilustrować algorytmu na grze PacMan. Wystarczy prosty program demo, do którego graf wprowadza się w jawnej postaci (np. macierzy sąsiedztwa), albo nawet jest on zawarty w kodzie na stałe.

Przykładowe pytania sprawdzające