Мне дали задачу, которая требует минимального дерева и оптимального дерева для графа, но наряду со стоимостью ребра нам также дают максимальное значение traffi c, а также значение traffi c для каждый узел, кроме первого. Мне известны алгоритмы Призмы и Крускала, но они не учитывают второй параметр, я пытался, но не смог найти алгоритм, способный учесть оба.
Как я понимаю, трафик * 1012 Параметр * предназначен для аннулирования деревьев, например, для следующего Графика у нас есть все веса ребер, а также трафик c для всех узлов, кроме первого.
Использование Kruskal или Prism мы можем обнаружить, что MST (минимальное связующее дерево) является следующим . Однако учитывается ли максимально допустимый трафик c, который в данном случае равен 11, и мы определяем трафик c для данного маршрута в этом дереве как сумму всех потоков между узлом источника и узел назначения, мы находим, что маршрут от узла 1 к узлу 5 имеет узлы 1, 3, 4 и 5, в то время как мы знаем, что T3, T4 и T5 имеют трафик c 6, 4 и 2 соответственно, и они добавляют до 12, что превысит максимальный трафик c и сделает недействительным mst для этого случая, вопрос в том, существуют ли какие-либо алгоритмы, которые учитывают две переменные одновременно.