Многоступенчатый граф 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 .