DAA - Grafico multistadio
Un grafico a più fasi G = (V, E) è un grafo diretto in cui sono partizionati i vertici k (dove k > 1) numero di sottoinsiemi disgiunti S = {s1,s2,…,sk}tale che l'arco (u, v) sia in E, allora u Є s i e v Є s 1 + 1 per alcuni sottoinsiemi nella partizione e |s1| = |sk| = 1.
Il vertice s Є s1 si chiama source e il vertice t Є sk è chiamato sink.
Gdi solito si presume che sia un grafico ponderato. In questo grafico, il costo di un arco (i, j) è rappresentato da c (i, j) . Quindi, il costo del percorso dalla fontes affondare t è la somma dei costi di ciascun bordo in questo percorso.
Il problema del grafico multistadio è trovare il percorso con il minimo costo dalla sorgente s affondare t.
Esempio
Considera il seguente esempio per comprendere il concetto di grafico multistadio.
Secondo la formula, dobbiamo calcolare il costo (i, j) utilizzando i seguenti passaggi
Passaggio 1: costo (K-2, j)
In questa fase, tre nodi (nodo 4, 5. 6) vengono selezionati come j. Quindi, abbiamo tre opzioni per scegliere il costo minimo in questo passaggio.
Costo (3, 4) = min {c (4, 7) + Costo (7, 9), c (4, 8) + Costo (8, 9)} = 7
Costo (3, 5) = min {c (5, 7) + Costo (7, 9), c (5, 8) + Costo (8, 9)} = 5
Costo (3, 6) = min {c (6, 7) + Costo (7, 9), c (6, 8) + Costo (8, 9)} = 5
Passaggio 2: costo (K-3, j)
Due nodi sono selezionati come j perché allo stadio k - 3 = 2 ci sono due nodi, 2 e 3. Quindi, il valore i = 2 e j = 2 e 3.
Costo (2, 2) = min {c (2, 4) + Costo (4, 8) + Costo (8, 9), c (2, 6) +
Costo (6, 8) + Costo (8, 9)} = 8
Costo (2, 3) = {c (3, 4) + Costo (4, 8) + Costo (8, 9), c (3, 5) + Costo (5, 8) + Costo (8, 9), c (3, 6) + Costo (6, 8) + Costo (8, 9)} = 10
Passaggio 3: costo (K-4, j)
Costo (1, 1) = {c (1, 2) + Costo (2, 6) + Costo (6, 8) + Costo (8, 9), c (1, 3) + Costo (3, 5) + Costo (5, 8) + Costo (8, 9))} = 12
c (1, 3) + Costo (3, 6) + Costo (6, 8 + Costo (8, 9))} = 13
Quindi, il percorso che ha il costo minimo è 1→ 3→ 5→ 8→ 9.