алгоритм выбора кратчайшего маршрута
Источник: MIT

Исследователи из МТИ предложили новый алгоритм решения задачи максимального потока, более эффективный чем существующие, поскольку его быстродействие уменьшается в обратной пропорции к сложности задачи. В числе возможных применений алгоритма разработчики называют выбор самого быстрого пути передачи данных по сети с высоким трафиком. Алгоритмы нахождения максимального потока действуют путем построения графа, вершины которого представляют конечные точки маршрутов, а ребра — связи между ними; затем выбирается оптимальный путь с учетом предельной пропускной способности каждой вершины. Обычно ребра при этом добавляются по одному, и при большом их количестве время выполнения алгоритма и затрачиваемые ресурсы могут вырасти колоссально. Новый алгоритм проверяет все возможные пути одновременно и при этом распознает узкие места сети.