Алгоритм пропускной способности графика

Question

У меня задача вычислить максимальную пропускную способность на графике.

Самый простой способ описания графика - int[][]. Внутренний массив узлов в графике, и внешний массив является расстоянием между подключением каждого узла в графе, например:

new int[][] { 
    {0, 5, 0, 0}, // node 0 (the "source") 
    {0, 0, 4, 0}, // node 1 
    {0, 0, 0, 8}, // node 2 
    {0, 0, 0, 0} // node 3 (the "destination") 
} 

Таким образом, чтобы получить от node 0 (источник), чтобы node 3 (конечного пункта «максимальная пропускная способность» будет 4 в свою очередь, потому что:

• 5 пакетов могут перейти от узла 0 к узлу 1
• 4 пакетов могут идти от узла 1 к узлу 2
• 8 пакеты могут идти от узла 2 к узлу 3

На основе «в свою очередь», узкое место между node 1 и node 2, где максимальная пропускная способность равна 4.

Может кто-то момент мне алгоритм, который позволит решить эту «максимальная пропускная способность» проблему любой заданный граф, определенный таким образом как int[][] и заданный source и destination узлов?

Примерный граф должен быть расширен несколькими «источниками» и «пунктами назначения», где мне нужно будет вычислить максимальную пропускную способность всей системы при любом заданном «повороте».

Буду признателен за помощь в виде алгоритмов для изучения или «псевдокода».

Answer 1

Maximum flow problem является то, что вы ищете:

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

Edmonds–Karp algorithm является обычным алгоритмом для нахождения максимального потока:

В информатике, алгоритм Эдмондс-Карп является реализацией методы Форда-Фалкерсон для вычисления максимального потока в сети потока в O (VE) время.

Как видно из Pseudocode, это не сложный алгоритм, когда дело доходит до реализации. Вот также C++ implementation.

Minimum cut может быть объединен с максимальной проблемой потока, с тем чтобы найти узкое место (может быть более чем один):

Разрез в сети потока, который отделяет источник и раковину вершину и сводит к минимуму общий вес по краям, которые направлены со стороны источника разреза на сторону раковины разреза. Как показано в теореме о минимальном разрезе максимального потока, вес этого разреза равен максимальному объему потока, который может быть отправлен из источника в приемник в данной сети.

Минимальный разрез использует максимальный расход и ищет первые кромки, которые находятся в емкости.

Подробнее в Max Flow, Min Cut.