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

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

Вершина s Є s 1 называется источником, а вершина t Є s k называется стоком .

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), с (1, 3) + Стоимость (3, 5) + Стоимость (5, 8) + Стоимость (8, 9))} = 12

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

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