5996833050

Do zapamiętywania pól nadaje się tradycyjna kolejka, którą nazwiemy

Q

Algorytm:

Krok 0. Przyjąć, że na początku wszystkie pola sąnre-odwiedzone. Krok 1. Umieścić w kolejce Q pole s. W polu s umieścić liczbę 0. Krok 2. Dopóki kolejka Q nie jest pusta, wykonywać kroki 3-5.

Krok 3. Usuń z kolejki Q jej pierwszy element (pole i’).

Krok 4. Dla każdego pola sąsiedniego względem v i nie oddzielonego od niego ścianą wykonaj krok 5.

Krok 5. Jeśli pole w nie było jeszcze odwiedzone, to umieścić w nim liczbę o jeden większą od liczby w polu v. Jeśli pole w zawiera wyjście, to przejdź do kroku 6, a w przeciwnym razie dołącz pole w na końcu kolejki Q.

Krok 6. {Budujemy od końca listę pól tworzących najkrótszą drogę z pola i do pola w na którym zakończył działanie krok 5. J Dopóki w nie jest polem s : za kolejne (od końca ) pole drogi przyjąć w i za nową wartość w przyjąć pole sąsiednie względem w, w którym znajduje się liczba o jeden mniejsza od liczby znajdującej się w obecnym polu w.

Algorytm ten jest szczególnym przypadkiem algorytmu Dijkstry wyznaczania najkrótszej drogi w dowolnej sieci połączeń, w której odległości między punktami są nieujemne (np. problem komiwojażera).