Witam :)
Aktualnie pracuje nad pewnym systemem. Mam do opracowania moduł do odnajdywania najkrótszej drogi, jednak nie jest to wykres, lecz coś co wygląda m-w tak:
Generalnei chodzi w tym o to, że wybieramy sobie 2 punkty, 1. start 2. koniec. Te szare kreski to połączenia, którm=ymi możemy podróżować. Zastanawiam się czy A* jest w ogóle dobrym wyborem, bo jakoś ciężko mi zauważyć analogię.
Byćmoże ktoś z Was już zajmował się podobną sprawą?
Pozdrawiam
Przydałoby się trochę więcej informacjii... Na przykład w jakiej postaci masz dane wejściowe, czym się różnią wierzchołki żółte od zielonych, itd, itp.
Poznaj wszystkie główne algorytmy wyszukiwania ścieżki i wybierz najlepszy.
Kolory nie mają znaczenia, odległości również.
Zresztą już znalazłem odpowiedni algorytm, napisałem implementację i działa ;-)
Chodzi o algorytm dijkstra.
Jeżeli odległości nie mają znaczenia, to nie potrzeba Dijkstry - wystarczy zwykłe przechodzenie grafu wszerz.
Jeżeli graf jest duży, to można to znacznie przyspieszyć szukając drogi jednocześnie z początku i końca.
Przeszukiwanie wszerz odwołuje się do grafu, w którym mamy "root node", tutaj nie mamy, konkretniej jest on zmienny - użytkownik sam ustala.
A* to ulepszona wersja Dijkstry. Jak zależy Ci na czasie działania, możesz do A* wrócić ...
Wspomniany przez ciebie "root node" to nic innego jak wierzchołek startowy [glowa]