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 = {s₁,s₂,…,s_k}tale che l'arco (u, v) sia in E, allora u Є s _i e v Є s _{1 + 1} per alcuni sottoinsiemi nella partizione e |s₁| = |s_k| = 1.

Il vertice s Є s₁ si chiama source e il vertice t Є s_k è 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.