DAA - Gráfico Multiestágio

Um gráfico de vários estágios G = (V, E) é um gráfico direcionado onde os vértices são particionados em k (Onde k > 1) número de subconjuntos disjuntos S = {s₁,s₂,…,s_k}tal que o bordo (u, v) é em E, em seguida, u Є s _i e v Є s _{1 + 1} para alguns subconjuntos na partição e |s₁| = |s_k| = 1.

O vértice s Є s₁ é chamado de source e o vértice t Є s_k é chamado sink.

Ggeralmente é considerado um gráfico ponderado. Neste gráfico, o custo de uma aresta (i, j) é representado por c (i, j) . Portanto, o custo do caminho da origems afundar t é a soma dos custos de cada aresta neste caminho.

O problema do gráfico de múltiplos estágios é encontrar o caminho com custo mínimo da origem s afundar t.

Exemplo

Considere o exemplo a seguir para entender o conceito de gráfico de vários estágios.

De acordo com a fórmula, temos que calcular o custo (i, j) usando as seguintes etapas

Etapa 1: Custo (K-2, j)

Nesta etapa, três nós (nó 4, 5. 6) são selecionados como j. Portanto, temos três opções para escolher o custo mínimo nesta etapa.

Custo (3, 4) = min {c (4, 7) + Custo (7, 9), c (4, 8) + Custo (8, 9)} = 7

Custo (3, 5) = min {c (5, 7) + Custo (7, 9), c (5, 8) + Custo (8, 9)} = 5

Custo (3, 6) = min {c (6, 7) + Custo (7, 9), c (6, 8) + Custo (8, 9)} = 5

Etapa 2: Custo (K-3, j)

Dois nós são selecionados como j porque no estágio k - 3 = 2 há dois nós, 2 e 3. Portanto, o valor i = 2 ej = 2 e 3.

Custo (2, 2) = min {c (2, 4) + Custo (4, 8) + Custo (8, 9), c (2, 6) +

Custo (6, 8) + Custo (8, 9)} = 8

Custo (2, 3) = {c (3, 4) + Custo (4, 8) + Custo (8, 9), c (3, 5) + Custo (5, 8) + Custo (8, 9), c (3, 6) + Custo (6, 8) + Custo (8, 9)} = 10

Etapa 3: Custo (K-4, j)

Custo (1, 1) = {c (1, 2) + Custo (2, 6) + Custo (6, 8) + Custo (8, 9), c (1, 3) + Custo (3, 5) + Custo (5, 8) + Custo (8, 9))} = 12

c (1, 3) + Custo (3, 6) + Custo (6, 8 + Custo (8, 9))} = 13

Portanto, o caminho com o custo mínimo é 1→ 3→ 5→ 8→ 9.