Matematyka.pl

Potrzebny jest mi taki algorytm, który na wejściu dostawałby:

• tablicę \(\displaystyle{ n \cdot n}\) punktów
• listę obszarów zabronionych w kształcie prostokątów
• dwa punkty

Chciałbym, żeby ten algorytm znajdywał najkrótszą odległość pomiędzy tymi dwoma punktami, bez przechodzenia przez obszary zabronione.

Jedyny pomysł to sprawdzenie wszystkich możliwości postaci łamanych pomiędzy punktami i wierzchołkami obszarów zabronionych, sprawdzenie które są dopuszczalne, a które przez te obszary przechodzą i na koniec znalezienia miniumum.

Jednak nie uśmiecha mi się pisanie go(chyba, że nie będzie innego wyjścia :p ), więc mam takie pytanie czy ktoś już napisał kiedyś taką funkcję i jest ona w jakieś bibliotece C++/ albo jest jej pseudokod gdzieś w internecie? Prawdopodobnie będzie trzeba ułożyć graf z tych wierzchołków i znalezienie algorytmem Dijkstry najkrótszą ścieżkę.

Edit. Algorytm DiJkstry znajdę, bardziej mi chodzi o sprawdzanie czy ścieżka jest dopuszczalna, czy zabroniona.

Używając Dijkstry operujesz na grafie, więc nie rób krawędzi z obszaru niezabronionego do zabronionego.
Do takich rzeczy najczęściej używa się algorytmu A*.
Jeżeli krawędzie nie mają wag, to wystarczy BFS.