DAA - Graphique à plusieurs étages

Un graphique à plusieurs niveaux G = (V, E) est un graphe orienté où les sommets sont partitionnés en k (où k > 1) nombre de sous-ensembles disjoints S = {s₁,s₂,…,s_k}tel que l'arête (u, v) est dans E, alors u Є s _i et v Є s _{1 + 1} pour certains sous-ensembles de la partition et |s₁| = |s_k| = 1.

Le sommet s Є s₁ s'appelle le source et le sommet t Є s_k est appelé sink.

Gest généralement supposé être un graphique pondéré. Dans ce graphique, le coût d'une arête (i, j) est représenté par c (i, j) . Par conséquent, le coût du chemin depuis la sources couler t est la somme des coûts de chaque arête de ce chemin.

Le problème du graphe en plusieurs étapes consiste à trouver le chemin avec un coût minimum à partir de la source s couler t.

Exemple

Prenons l'exemple suivant pour comprendre le concept de graphe à plusieurs étages.

Selon la formule, nous devons calculer le coût (i, j) en suivant les étapes suivantes

Étape 1: Coût (K-2, j)

Dans cette étape, trois nœuds (nœuds 4, 5. 6) sont sélectionnés comme j. Par conséquent, nous avons trois options pour choisir le coût minimum à cette étape.

Coût (3, 4) = min {c (4, 7) + Coût (7, 9), c (4, 8) + Coût (8, 9)} = 7

Coût (3, 5) = min {c (5, 7) + Coût (7, 9), c (5, 8) + Coût (8, 9)} = 5

Coût (3, 6) = min {c (6, 7) + Coût (7, 9), c (6, 8) + Coût (8, 9)} = 5

Étape 2: Coût (K-3, j)

Deux nœuds sont sélectionnés comme j car à l'étape k - 3 = 2, il y a deux nœuds, 2 et 3. Ainsi, la valeur i = 2 et j = 2 et 3.

Coût (2, 2) = min {c (2, 4) + Coût (4, 8) + Coût (8, 9), c (2, 6) +

Coût (6, 8) + Coût (8, 9)} = 8

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

Étape 3: Coût (K-4, j)

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

c (1, 3) + Coût (3, 6) + Coût (6, 8 + Coût (8, 9))} = 13

Par conséquent, le chemin ayant le coût minimum est 1→ 3→ 5→ 8→ 9.