Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C++] Graf - poszukiwanie ścieżki z najmniejszą liczbą punktów

Ostatnio zmodyfikowano 2016-03-12 16:09
Autor Wiadomość
MirekWWA
Temat założony przez niniejszego użytkownika
[C++] Graf - poszukiwanie ścieżki z najmniejszą liczbą punktów
» 2016-03-11 18:37:11
Cześć

Nie jestem w stanie wpaść na pomysł czego użyć do znalezienia drogi w grafie spójnym nieskierowanym, która będzie miała w sobie jak najmniej wysp/obszarów/miast, czy czegokolwiek innego. Jeśli dane punkty są połączone, to nie jest dla mnie ważna odległość między nimi. Będę bardzo wdzięczny za jakąś podpowiedź.

Pozdrawiam
P-145904
mokrowski
» 2016-03-11 20:12:51
https://pl.wikipedia.org/wiki/Algorytm_Dijkstry
http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/index.html
P-145905
MirekWWA
Temat założony przez niniejszego użytkownika
» 2016-03-12 13:37:43
Dziękuję za odpowiedź. Spodziewałem się, że trzeba będzie użyć zmodyfikowanej wersji Dijkstry, natomiast nie rozumiem na jakiej zasadzie taka modyfikacja miałaby polegać. Jak mi wiadomo algorytm przeszukuje najkrótszą ścieżkę po danych wagach mostów, czyli ścieżka może być przecinana dużą liczbą punktów byleby droga była krótka.
P-145924
mokrowski
» 2016-03-12 16:09:07
Przyjmij jednostkową stałą wagę dla krawędzi i tyle:)
P-145930
« 1 »
  Strona 1 z 1