Dojscie w grafie do punktu w okreslonym czasie

0

Witam, mam problem z pewnym zadaniem. Mam graf z wagami nieujemnymi dodatkowo kazdy wierzcholek ma pewna wartosc t>0. Wierzcholki sa podzielone na dwie grupy A i B. Trzeba sprawdzic czy zaistnieje sytuacja ze z jakiegos wierzcholka B dojdzie sie do wierzcholka nr 1 grupy A. Jesli dochodzimy do wierzcholka A(ktory nie jest nr 1) do idziemy dalej jedynie jesli waga krawedzi prowadzacej do miasta jest < t danego wierzcholka.

Zapewne trzeba wykorzystac tu ktorys z podstawowych algorytmow do grafow, ale kompletnie nie mam pomyslu jak wykorzystac tutaj.

Btw. Poprawilem tym razem temat ;D wtedy tez mialo byc poprawnie ale zapomnialem zmienic;) moj blad

Shalom dal rozwiazanie:

  1. Robimy z tego grafu graf skierowany
  2. Kasujemy krawędzie takie które mają wagę >= niż t w wierzchołku z którego wychodzą
  3. Odwracamy zwroty wszystkich krawędzi na przeciwne
  4. Puszczamy sobie bfs z pierwszego wierzchołka z A i rozlewamy się po grafie tak długo aż nie skończą nam się wierzchołki, albo nie trafimy na coś z B.

ale nie napisalem zasadniczej sprawy ze t i wagi grafow sa postrzegane jako czas wiec sie sumuje i podany sposob troche sie komplikuje.
Jesli idziemy np. z 4->3->1 (zakladamy ze przez pkt 3 idzie dalej )i krawedzie grafu miedzy 4-3 i 3-1 maja odpowiednio 5,6 to t wierzcholka 1 musi byc >11 aby bylo zaliczone;
Jakby miał jeszcze jakis pomysl to wielki dzieki.

ps. Shalom dzieki za zainteresowanie w poprzednim temacie

0

Naiwny sposób to puszczenie zoptymalizowanego algorytmu Dijkstry od strony każdego z wierzchołków B (optymalizacja polegałaby na odcinaniu wierzchołków które po relaksacji miałyby wartość >=t w tym wierzchołku). Nie mam w tej chwili pomyslu na nic lepszego ;]

1 użytkowników online, w tym zalogowanych: 0, gości: 1