Graph algorytm do obliczania wartości węzła w oparciu o sąsiednich węzłach

Question

chciałbym zrobić algorytm wykres aktualizacje/oblicza wartość węzła f(n) jako funkcję każdego z wartościami f(n) z sąsiednich węzłów.

• Wykres jest skierowany.
• Każdy węzeł ma początkową wartość f (n).
• Każda krawędź nie ma ŻADNYCH kosztów (0).
• Wartość każdego węzła to maksymalna jego aktualna wartość oraz wartość dla każdego sąsiedniego węzła (skierowany wykres, więc sąsiadami są te, od których dany węzeł ma krawędzie przychodzące).

Bardziej formalnie,

f(n) = max(f(n),max_i(f(n_i))), where i from neighbor 1 to neighbor k. 

mogę wyobrazić kilka sposobów działania tak, jednak nie wiem, w jakim stopniu są optymalne.

Czy każdy może podać sugestie i komentarze (czy uważasz, że Twoja sugestia jest optymalna) czy sugerować istniejący algorytm wykresu, który mogę zaadaptować?

Answer 1

Zastrzeżenia patentowe

1. W każdym Strongly Connected ComponentV na wykresie, wartości wszystkich wierzchołków tego SCC taki sam końcowy wynik.
   "Dowód" (wytyczna): wykonując propogację w tym SCC, można iteracyjnie ustawić wszystkie wyniki do maksymalnej wartości znalezionej w tym SCC.

2. W DAG wartość każdego wierzchołka wynosi max{v,parent(v) | for all parents of v} (definicja), a wynik można znaleźć w pojedynczej iteracji od początku do końca.
   "Dowód" (wytyczna): Nie ma "tylnych krawędzi", więc jeśli znasz ostateczne wartości wszystkich rodziców, znasz ostateczną wartość każdego wierzchołka. Poprzez indukcję (podstawą są wszystkie źródła) - można uzyskać fakt, że pojedyncza iteracja wystarczy do określenia ostatecznego wyniku.

3. Wiadomo również, że wykres G' reprezentujący SCC wykres g to DAG.

Z powyższego można wyprowadzić prostą algorytm:

1. FING SCC maksymalnych na wykresach (można zrobić z Tarjan algorithm), a także tworzyć SCC wykres. Niech to będzie G'. Zauważ, że G' to DAG.
2. Dla każdego SCC V: ustaw f'(V) = max{v | v in V} (intuicyjnie - ustaw wartość każdego SCC jako wartość maksymalną w tym SCC).
3. Topological sort na wykresie G'.
4. Wykonaj pojedyncze przejście zgodnie z topologicznym sortem znalezionym w (3) - i obliczyć f '(V) dla każdego wierzchołka w G' według jego rodziców.
5. ustawiona f(v) = f'(V) (gdzie v jest SCC V)

Złożoność:

1. Tarjan i tworzenia G' jest O(V+E)
2. Znalezienie f”jest również liniowy w rozmiarze z wykres - O(V+E)
3. Sortowanie według rodzaju topologicznego w O(V+E)
4. Przejazd pojedynczy - liniowy: O(V+E)
5. Daje końcowe wyniki: liniowy!

więc powyższy algorytm jest liniowy w wielkości wykresu - O(V+E)