DAA - многоступенчатый график

Многоступенчатый граф G = (V, E) ориентированный граф, в котором вершины разбиты на k (где k > 1) количество непересекающихся подмножеств S = {s1,s2,…,sk}такое, что ребро (u, v) находится в E, то u Є s i и v Є s 1 + 1 для некоторых подмножеств в разбиении и |s1| = |sk| = 1.

Вершина s Є s1 называется source и вершина t Є sk называется sink.

Gобычно считается взвешенным графом. В этом графе стоимость ребра (i, j) представлена ​​как c (i, j) . Следовательно, стоимость пути от источникаs тонуть t сумма затрат каждого ребра на этом пути.

Задача многоступенчатого графа - найти путь с минимальными затратами из источника s тонуть t.

пример

Рассмотрим следующий пример, чтобы понять концепцию многоступенчатого графа.

По формуле надо рассчитать стоимость (i, j) используя следующие шаги

Шаг-1: Стоимость (K-2, j)

На этом шаге три узла (узел 4, 5. 6) выбираются как j. Следовательно, у нас есть три варианта выбора минимальной стоимости на этом этапе.

Стоимость (3, 4) = min {c (4, 7) + Стоимость (7, 9), c (4, 8) + Стоимость (8, 9)} = 7

Стоимость (3, 5) = min {c (5, 7) + Стоимость (7, 9), c (5, 8) + Стоимость (8, 9)} = 5

Стоимость (3, 6) = min {c (6, 7) + Стоимость (7, 9), c (6, 8) + Стоимость (8, 9)} = 5

Шаг 2: Стоимость (K-3, j)

Два узла выбраны как j, потому что на этапе k - 3 = 2 есть два узла, 2 и 3. Итак, значение i = 2 и j = 2 и 3.

Стоимость (2, 2) = min {c (2, 4) + Стоимость (4, 8) + Стоимость (8, 9), c (2, 6) +

Стоимость (6, 8) + Стоимость (8, 9)} = 8

Стоимость (2, 3) = {c (3, 4) + Стоимость (4, 8) + Стоимость (8, 9), c (3, 5) + Стоимость (5, 8) + Стоимость (8, 9), c (3, 6) + Стоимость (6, 8) + Стоимость (8, 9)} = 10

Шаг 3: Стоимость (K-4, j)

Стоимость (1, 1) = {c (1, 2) + Стоимость (2, 6) + Стоимость (6, 8) + Стоимость (8, 9), c (1, 3) + Стоимость (3, 5) + Стоимость (5, 8) + Стоимость (8, 9))} = 12

c (1, 3) + Стоимость (3, 6) + Стоимость (6, 8 + Стоимость (8, 9))} = 13

Следовательно, путь с минимальной стоимостью равен 1→ 3→ 5→ 8→ 9.