algoritmo grafico per calcolare valori nodi in base ai nodi adiacenti

Question

desidero fare un algoritmo grafico che aggiornamenti/calcola il valore di un nodo f(n) in funzione di ciascuna delle f(n) valori di nodi adiacenti.

• Il grafico è diretto.
• Ogni nodo ha come valore f (n) iniziale.
• Ogni lato non ha costi (0).
• Il valore di ogni nodo è il massimo del suo valore corrente e il valore di ciascun nodo adiacente (grafico diretto, quindi i vicini sono quelli da cui il nodo ha bordi in entrata).

Più formalmente,

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

mi può visualizzare alcuni modi di fare così, però non so fino a che punto sono ottimali.

Qualcuno può fornire suggerimenti e commenti (se pensi che il tuo suggerimento sia ottimale) o suggerire un algoritmo grafico esistente che posso adattare?

Answer 1

rivendicazioni:

1. In ogni Strongly Connected ComponentV nel grafico, i valori di tutti i vertici in questo SCC hanno lo stesso punteggio finale.
   "Proof" (linea guida): eseguendo la propagazione in questo SCC, è possibile impostare iterativamente tutti i punteggi sul valore massimo trovato in questo SCC.

2. In un DAG, il valore di ogni vertice è max{v,parent(v) | for all parents of v} (definizione) e il punteggio può essere trovato all'interno di una singola iterazione dall'inizio alla fine.
   "Proof" (linea guida): non ci sono "spigoli", quindi se si conoscono i valori finali di tutti i genitori, si conosce il valore finale di ciascun vertice. Per induzione (la base è tutte le fonti) - si può arrivare al fatto che una singola iterazione è sufficiente per determinare il punteggio finale.

3. Inoltre, è noto che il grafico G' che rappresenta l'SCC di un grafico g è un DAG.

Da quanto sopra si può ricavare un semplice algoritmo :

1. Fing SCC massime nei grafici (può essere fatto con Tarjan algorithm), e creare il grafico SCC. Lascia che sia G'. Si noti che G' è un DAG.
2. Per ogni SCC V: impostare f'(V) = max{v | v in V} (intuitivamente - impostare il valore di ciascun SCC come valore massimo in questo SCC).
3. Topological sort il grafico G'.
4. Effettua un singolo attraversamento in base al tipo topologico trovato in (3) e calcola la f '(V) per ciascun vertice in G' in base ai genitori.
5. Impostare f(v) = f'(V) (dove v è nell'SCC V)

Complessità:

1. Tarjan e creando G' è O(V+E)
2. Trovare f' è anche lineare nella dimensione del grafico - O(V+E)
3. Ordinamento topologico eseguito in O(V+E)
4. Single traversal - linear: O(V+E)
5. Dare i punteggi finali: lineare!

Quindi il comando precedente algoritmo è lineare nella dimensione del grafico-O(V+E)